C++で解くバイナリマトリックスの最大10進値パス問題

問題概要

与えられた正方バイナリ配列（2次元配列）において、左上の要素であるインデックス [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]

したがって、10進値は以下のように計算されます。
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}
}

出力

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 は 2 のべき乗を表す
int Max(int m[][side], int i, int j, int pw){
    // 行列の境界外の場合
    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関数
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