首页 > 代码库 > HDU 1278

HDU 1278

2024-07-21 12:14:34   223人阅读

题目大意：

从（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\n",dfs(1,1));80     }81     return 0;82 }

 

HDU 1278


联系
我们