C++のバイナリマトリックスの最大10進値パス

与えられたタスクは、与えられた正方形のバイナリ配列の左上の要素から右下の要素へのパスを移動するときに取得できる最大の整数値を見つけることです。つまり、インデックス[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（）関数で、2D配列int m [] [4]を作成して行列を格納し、Max（m、0、0、0）

  を呼び出します。

• max（）関数で、最初に（i> =side || j> =side）かどうかを確認します。もしそうなら、それは私たちがマトリックスの境界から外れていて、0を返すことを意味します。

• 新しい変数intansを作成し、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