กำหนดภารกิจคือค้นหาค่าจำนวนเต็มสูงสุดที่สามารถรับได้ขณะเดินทางในเส้นทางจากองค์ประกอบด้านซ้ายบนไปยังองค์ประกอบด้านล่างขวาของอาร์เรย์ไบนารีสแควร์ที่กำหนด นั่นคือ เริ่มจากดัชนี [0][0] ถึงดัชนี [n - 1][n - 1].
ในขณะที่ครอบคลุมเส้นทาง เราสามารถย้ายไปทางขวา ([i][j + 1]) หรือไปด้านล่างเท่านั้น ([i + 1][j])
ค่าจำนวนเต็มจะคำนวณโดยใช้บิตของเส้นทางที่ข้ามผ่าน
ตอนนี้มาทำความเข้าใจสิ่งที่เราต้องทำโดยใช้ตัวอย่าง -
อินพุต
m = {
{1, 1, 1, 1},
{0, 0, 1, 0},
{1, 0, 1, 1},
{0, 1, 1, 1}
} ผลลัพธ์
127
คำอธิบาย
เส้นทางที่เราใช้คือ [0, 0] →[0, 1] → [0, 2] → [1, 2] → [2, 2] → [3, 2] →[3, 3]
ดังนั้นค่าทศนิยมจะกลายเป็น =1*(2 0 ) + 1*(2 1 ) + 1*(2 2 ) + 1*(2 3 ) + 1*(2 4 ) + 1*(2 5 ) + 1*(2 6 )
=1 + 2 + 4 + 8 + 16 + 32 + 64
=127
อินพุต
m = {
{1, 0, 1, 1},
{0, 0, 1, 0},
{1, 0, 0, 1},
{0, 1, 1, 1}
} ผลลัพธ์
109
แนวทางที่ใช้ในโปรแกรมด้านล่างดังนี้
-
ขั้นแรกให้กำหนดขนาดด้านของเมทริกซ์สี่เหลี่ยมจัตุรัสที่ด้านบนโดยใช้ #define
-
ในฟังก์ชัน main() สร้างอาร์เรย์ 2 มิติ int m[][4] เพื่อเก็บเมทริกซ์และเรียก Max(m, 0, 0, 0)
-
ในฟังก์ชัน max() ก่อนตรวจสอบว่า (i>=side || j>=side ) หากเป็นเช่นนั้น แสดงว่าเราอยู่นอกขอบเขตของเมทริกซ์และคืนค่าเป็น 0
-
สร้างตัวแปร int ans ใหม่และใส่ ans =max(Max(m, i, j+1, pw+1), Max(m, i+1, j, pw+1))
-
จากนั้นตรวจสอบว่า (m[i][j] ==1) ถ้าใช่ ให้คืนค่า pow(2, pw) + ans.
-
มิฉะนั้นเพียงส่งคืน ans
ตัวอย่าง
#include<bits/stdc++.h>
using namespace std;
#define side 4
// pw is power of 2
int Max(int m[][side], int i, int j, int pw){
// Out of boundary
if (i >= side || j >= side )
return 0;
int ans = max(Max(m, i, j+1, pw+1), Max(m, i+1, j, pw+1));
if (m[i][j] == 1)
return pow(2, pw) + ans;
else
return ans;
}
//main function
int main(){
int m[][4] = {{1, 1, 1, 1},{0, 0, 1, 0},{1, 0, 1, 1},{0, 1, 1, 1}};
cout << Max(m, 0, 0, 0);
return 0;
} ผลลัพธ์
127
