题目描述 设有一个n×m(小于100)的方格，在方格中去掉某些点，方格中的数字代表距离（为小于100的数，如果为0表示去掉的点），试找出一条从A(左上角)到B（右下角）的路径，经过的距离和为最小（此时称为最小代价），从A出发的方向只能向右，或者向下。
分析 类似于数字金字塔，但是输出之前要记录路径
#include <iostream> #include <cstdio> int n,m,i,j,a[201][201],w[201][201][3],p; void print(int x,int y) { if (x==0&&y==0) return; print(w[x][y][1],w[x][y][2]); if (x!=n||y!=m) printf("(%d,%d)->",x,y); else printf("(%d,%d)",x,y); } int max(int k,int l) { if (k!=0&&k<l&&l!=0||k!=0&&l==0) { w[i][j][1]=i-1; w[i][j][2]=j; return k; } else if (l!=0) { w[i][j][1]=i; w[i][j][2]=j-1; return l; } } int main() { scanf("%d%d",&n,&m); for (i=1;i<=n;i++) for (j=1;j<=m;j++) scanf("%d",&a[i][j]); p=a[n][m]; for (i=2;i<=n;i++) { a[i][1]=a[i-1][1]+a[i][1]; a[1][i]=a[1][i-1]+a[1][i]; } for (i=2;i<=n;i++) { for (j=2;j<=m;j++) if (a[i][j]!=0) a[i][j]=a[i][j]+max(a[i-1][j],a[i][j-1]); } printf("(%d,%d)->",1,1); print(n,m); printf("\n"); printf("%d",a[n][m]-p); return 0; }