HDU-1428-漫步校园-白红宇

HDU-1428-漫步校园

阅读量：6446 次

发布时间：2019-06-23

本文共 2122 字，大约阅读时间需要 7 分钟。

链接：https://vjudge.net/problem/HDU-1428

题意：

LL最近沉迷于AC不能自拔，每天寝室、机房两点一线。由于长时间坐在电脑边，缺乏运动。他决定充分利用每次从寝室到机房的时间，在校园里散散步。整个HDU校园呈方形布局，可划分为n*n个小方格，代表各个区域。例如LL居住的18号宿舍位于校园的西北角，即方格(1,1)代表的地方，而机房所在的第三实验楼处于东南端的(n,n)。因有多条路线可以选择，LL希望每次的散步路线都不一样。另外，他考虑从A区域到B区域仅当存在一条从B到机房的路线比任何一条从A到机房的路线更近(否则可能永远都到不了机房了…)。现在他想知道的是，所有满足要求的路线一共有多少条。你能告诉他吗?

思路：

BFS先求每个点到终点的最短路。（刚开始以为只有往下方和右方WA了）

DFS对每个方向求，同时记录每个点到终点的路线。

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   using namespace std;typedef long long LL;const int MAXN = 50 + 10;const int INF = 99999999;int Next[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1}};int a[MAXN][MAXN];int dp[MAXN][MAXN];int Vis[MAXN][MAXN];LL res[MAXN][MAXN];int n;void Bfs(){ queue
                   
                    
                      > que; memset(Vis, 0, sizeof(Vis)); for (int i = 1;i <= n;i++) for (int j = 1;j <= n;j++) dp[i][j] = INF; dp[n][n] = a[n][n]; que.push(make_pair(n, n)); Vis[n][n] = 1; while (!que.empty()) { int nowx = que.front().first; int nowy = que.front().second; Vis[nowx][nowy] = 0; que.pop(); for (int i = 0;i < 4;i++) { int tx = nowx + Next[i][0]; int ty = nowy + Next[i][1]; if (tx < 1 || tx > n || ty < 1 || ty > n) continue; if (dp[tx][ty] > dp[nowx][nowy] + a[tx][ty]) { dp[tx][ty] = dp[nowx][nowy] + a[tx][ty]; if (Vis[tx][ty] == 0) { Vis[tx][ty] = 1; que.push(make_pair(tx, ty)); } } } }}LL Dfs(int x, int y){ if (x == n && y == n) return 1; if (res[x][y] != -1) return res[x][y]; res[x][y] = 0; for (int i = 0;i < 4;i++) { int tx = x + Next[i][0]; int ty = y + Next[i][1]; if (tx < 1 || tx > n || ty < 1 || ty > n) continue; if (dp[tx][ty] < dp[x][y]) res[x][y] += Dfs(tx, ty); } return res[x][y];}int main(){ while (cin >> n) { for (int i = 1;i <= n;i++) { for (int j = 1;j <= n;j++) cin >> a[i][j]; } Bfs(); /* for (int i = 1;i <= n;i++) { for (int j = 1;j <= n;j++) cout << dp[i][j] << ' ' ; cout << endl; } */ memset(res, -1, sizeof(res)); cout << Dfs(1, 1) << endl; } return 0;}/*31 2 3 45 6 7 81 2 3 4 */

转载于:https://www.cnblogs.com/YDDDD/p/10665766.html

你可能感兴趣的文章