C ++中二进制矩阵中的最大十进制值路径

Z时代
2024-01-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}
}

输出结果

说明

我们采取的路径是：[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()函数中创建一个二维数组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;
}
//主要功能
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;
}