数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学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}
}输出
127
解释
我们选择的路径是：[0, 0] →[0, 1] → [0, 2] → [1, 2] → [2, 2] → [3, 2] →[3, 3]
因此，十进制值变为 = 1*(20) + 1*(21) + 1*(22) + 1*(23) + 1*(24) + 1*(25) + 1*(26)
= 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()函数中创建一个二维数组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
更新于：2020年8月4日
104 次浏览
广告