题目大意：
从（1,1）到（n，n），每经过一个点都要花费一定的时间，问花最短时间的路径有多少条
dfs+dp
先用bfs把所有到n花费的时间逆向dp计算一遍
再用dfs不断找到前一个对应的较短路径的点不断搜索路径
1 #include <cstdio> 2 #include <cstring> 3 #include <queue> 4 using namespace std; 5 #define LL long long 6 #define N 52 7 8 struct node{ 9 int x,y; 10 }; 11 12 queue<node> q; 13 int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}},dp[N][N],mat[N][N],n; 14 LL s[N][N]; 15 16 void bfs() 17 { 18 dp[n][n]=mat[n][n]; 19 node a; 20 a.x=n,a.y=n; 21 q.push(a); 22 while(!q.empty()){ 23 node b=q.front(); 24 q.pop(); 25 for(int i=0;i<4;i++){ 26 int xx=b.x+dir[i][0]; 27 int yy=b.y+dir[i][1]; 28 if(xx>=1&&xx<=n&&yy>=1&&yy<=n){ 29 if(dp[xx][yy]==0||dp[xx][yy]>dp[b.x][b.y]+mat[xx][yy]){ 30 node c; 31 c.x=xx,c.y=yy; 32 q.push(c); 33 dp[xx][yy]=dp[b.x][b.y]+mat[xx][yy]; 34 } 35 } 36 } 37 } 38 } 39 40 LL dfs(int x,int y) 41 { 42 43 if(x==n&&y==n) return 1; 44 if(s[x][y]) return s[x][y];//在记忆化搜索中，就是利用已知的数据直接代入， 45 //避免重复计算，在此就是把数据保存在s中 46 for(int i=0;i<4;i++){ 47 int xx=x+dir[i][0]; 48 int yy=y+dir[i][1]; 49 if(xx>=1&&xx<=n&&yy>=1&&yy<=n){ 50 if(dp[xx][yy]<dp[x][y]){ 51 s[x][y]+=dfs(xx,yy); 52 } 53 } 54 } 55 return s[x][y]; 56 } 57 58 int main() 59 { 60 while(~scanf("%d",&n)){ 61 62 memset(dp,0,sizeof(dp)); 63 memset(s,0,sizeof(s)); 64 65 for(int i=1;i<=n;i++){ 66 for(int j=1;j<=n;j++){ 67 scanf("%d",&mat[i][j]); 68 } 69 } 70 71 bfs(); 72 73 /*for(int i=1;i<=n;i++){ 74 for(int j=1;j<=n;j++){ 75 printf("%d ",dp[i][j]); 76 } 77 puts(""); 78 }*/ 79 printf("%I64d ",dfs(1,1)); 80 } 81 return 0; 82 }