中国建设银行信用卡黑名单网站,工业设计在线网站,网站建设毕业答辩问题,大庆今天最新公告最小代价问题
Description
设有一个nm(小于100)的方格#xff08;如图所示#xff09;#xff0c;在方格中去掉某些点#xff0c;方格中的数字代表距离#xff08;为小于100的数#xff0c;如果为0表示去掉的点#xff09;#xff0c;试找出一条从A(左上角)到B#…最小代价问题
Description
设有一个n×m(小于100)的方格如图所示在方格中去掉某些点方格中的数字代表距离为小于100的数如果为0表示去掉的点试找出一条从A(左上角)到B右下角的路径经过的距离和为最小此时称为最小代价从A出发的方向只能向右或者向下。
Sample Input
4 4
4 10 7 0
3 2 2 9
0 7 0 4
11 6 12 1
Sample Output
(1,1)-(2,1)-(2,2)-(2,3)-(2,4)-(3,4)-(4,4)
24
解题思路
用递推的方式一步一步推还要判断是否是0 (0代表没有这个点),当这个点是最后一个点时减去这个点。(最后一个点不算)
#includecstdio
using namespace std;
int a[110][110],b[110][110],c[110][110],n,m;
void dg(int x,int y)
{if (x1y1){printf((1,1));return;}if (c[x][y]1) dg(x-1,y);else dg(x,y-1);printf(-(%d,%d),x,y);
}
int main()
{scanf(%d%d,n,m);for (int i1;in;i)for (int j1;jm;j){scanf(%d,a[i][j]);//读入因为当前位置的最小代价只和前面有关所以可以一起放在一起。if (i1j1) b[1][1]a[1][1];//b(1,1)没有上一步所以要直接加。if ((b[i-1][j]b[i][j-1]||b[i][j-1]0)b[i-1][j])//上面的数小一点或左边没有数还要判断上面是否为0{b[i][j]b[i-1][j]a[i][j];c[i][j]1;}if ((b[i-1][j]b[i][j-1]||b[i-1][j]0)b[i][j-1])//左面的数小一点或上边没有数还要判断左面是否为0b[i][j]b[i][j-1]a[i][j];if (a[i][j]0) b[i][j]0;//如果当前值为0清除b值}dg(n,m);printf(\n%d,b[n][m]-a[n][m]);
}
