我要评论取数字问题
题目
给定M*N的矩阵，其中的每个元素都是-10到10之间的整数。你的任务是从左上角（1，1）走到右下角（M，N），每一步只能向右或向下，并且不能走出矩阵的范围。你所经过的方格里面的数字都必须被选取，请找出一条最合适的道路，使得在路上被选取的数字之和是尽可能小的正整数。
输入
第一行两个整数M，N，（2<=M,N<=10），分别表示矩阵的行和列的数目。接下来的M行，每行包括N个整数，就是矩阵中的每一行的N个元素。
输出
仅一行一个整数，表示所选道路上数字之和所能达到的最小的正整数。如果不能达到任何正整数就输出-1。
Sample Input
2 2
0 2
1 0Sample Output
1解题思路
这道题最大的一个陷阱不是有负数，而是许多人没有注意到一点：如果数组里只设正整数，不设负整数，那么这道题就会被扣掉几个点，如：
2 2
2 -4
-4 2样例很明显，由于0不属于正整数，所以本题输出-1
但如果没有设负数的范围，那么这个点相对而言与
2 2
2 -2
-2 2完全一样，而后者应输出的是2
这道题的范围为-1000~1000，所以我们定义布尔变量b[11][11][2001]，其中前两个是坐标，后一个是数值+1000，只有这样才能储存负数
最后输出时把结束点的最小为i使a[n][m][1000+i]为true
代码
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,a[11][11];
bool b[11][11][2001];
void dfs(int x,int y,int d)
{
b[x][y][d]=1;
if(x<n&&b[x+1][y][d+a[x+1][y]]==0)dfs(x+1,y,d+a[x+1][y]);//动态转移方程
if(y<m&&b[x][y+1][d+a[x][y+1]]==0)dfs(x,y+1,d+a[x][y+1]);//动态转移方程
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)scanf("%d",&a[i][j]);
}
dfs(1,1,1000+a[1][1]);
for(int i=1001;i<=2000;i++)
{
if(b[n][m][i])
{
cout<<i-1000;
return 0;
}
}
cout<<"-1";
return 0;
}本文地址：https://blog.csdn.net/zhanglili1597895/article/details/108178897
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请 点击进行留言回复，万千网友为您解惑！
网友评论