เส้นทางค่าทศนิยมสูงสุดในเมทริกซ์ไบนารีใน C++

ภารกิจคือการหาค่าจำนวนเต็มสูงสุดที่ได้จากการเดินทางในเส้นทางจากมุมซ้ายบนไปมุมขวาล่างของอาร์เรย์ไบนารีสี่เหลี่ยมจัตุรัส คือ จากดัชนี [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}
}

เอาต์พุต

คำอธิบาย

เส้นทางที่เดิน: [0,0] → [0,1] → [0,2] → [1,2] → [2,2] → [3,2] → [3,3]

ค่าทศนิยม = 1×2⁰ + 1×2¹ + 1×2² + 1×2³ + 1×2⁴ + 1×2⁵ + 1×2⁶ = 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}
}

เอาต์พุต

แนวทางที่ใช้ในโปรแกรมด้านล่าง

กำหนดขนาดด้านของเมทริกซ์สี่เหลี่ยมด้วย #define
ใน main() สร้างอาร์เรย์ 2D int m[][4] เรียก Max(m, 0, 0, 0)
ใน Max() ถ้า i ≥ side หรือ j ≥ side คืน 0 (ออกขอบเขต)
สร้างตัวแปร int 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;
}

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;
}