这一题是看了别人的blog才知道题目中求的path是长啥样的,可我还是木有从题面上看出path可以斜着走><
which is a 8-connected path vertically or horizontally. 特地强调vertically or horizontally是在干嘛啊??
dp[i][j]表示从第一行的某一格到这一格的energy,pre[i][j]表示[i,j]前一个状态的列数,最后打印路径直接递归即可,有点像Dijkstra的打印路径。
至于保证同等energy选最右边的path,从左往右状态转移时energy相等时也转移即可。
#include<iostream> #include<stdio.h> #include<cstdio> #include<stdlib.h> #include<vector> #include<string> #include<cstring> #include<cmath> #include<algorithm> #include<stack> #include<queue> #include <ctype.h> using namespace std; int T; int m; int n; int a[110][110]; int dp[110][110]; int pre[110][110]; void print_path(int r,int c) { if(r==1) { printf("%d ",c); return; } print_path(r-1,pre[r][c]);//pre[r][c]表示的是[r,c]的前一个状态的列数,之前写成pre[r-1][c]了。。调了好久 if(r==m) { printf("%d\n",c); } else { printf("%d ",c); } } int main() { freopen("input.txt","r",stdin); // freopen("data.txt","r",stdin); //freopen("out1.txt","w",stdout); scanf("%d",&T); for(int t=1;t<=T;t++) { memset(dp,0x3f,sizeof(dp)); memset(pre,0,sizeof(pre)); scanf("%d %d",&m,&n); for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { scanf("%d",&a[i][j]); } } for(int j=1;j<=n;j++) { dp[1][j]=a[1][j]; pre[1][j]=j; } for(int i=2;i<=m;i++) { for(int j=1;j<=n;j++)//how to deal with border?直接设成INF,状态就不会转移 { for(int k=j-1;k<=j+1;k++) { if(dp[i][j]>=dp[i-1][k]+a[i][j]) { dp[i][j]=dp[i-1][k]+a[i][j]; pre[i][j]=k; } } // cout<<i<<" "<<j <<" dp[i][j]: "<<dp[i][j]<<" k: "<<pre[i][j]<<endl; } } int mi=0x3f3f3f3f; int c=0; for(int j=1;j<=n;j++) { if(mi>=dp[m][j]) { mi=dp[m][j]; c=j; } } printf("Case %d\n",t); print_path(m,c); } return 0; }