本文主要是介绍HDU 1428 漫步校园 （搜索 + dp），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
OJ题目：click here ~~
题意分析：题目中有句话“他考虑从A区域到B区域仅当存在一条从B到机房的路线比任何一条从A到机房的路线更近(否则可能永远都到不了机房了…)。”，关键是对这句话的理解。此刻在A区域，选择下面要走的B区域的条件是，存在一条B区域到机房的路线比A区域到机房的所有路线都近，也就是说，存在一条B区域到机房的路线比A区域到机房的最短路线更近（比最短的近，也就能保证比所有都近了）。也就是说，B区域到机房的最短路线 比 A区域到机房的最短路线更近即可（最短的比它近，也就能保证至少存在一条比它近了）。下面就好办了，求出所有区域到机房的最短路径，再记忆划搜索一下就可以了。
AC_CODE
typedef long long LL;
int n;
const int inf = 100000000;
int dir[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
int grid[51][51];
int dist[51][51];//(i,j)到(n , n)的最短距离
LL dp[52][52];struct Node
{int x;int y;int dis;//(x, y)距离(n,n)的最短距离Node(){}Node(int i , int j , int k):x(i),y(j),dis(k){}friend bool operator<(const Node &A , const Node &B){return A.dis > B.dis;}
};bool cango(int x , int y)
{return 1 <= x && x <= n && 1 <= y && y <= n;
}void bfs()//计算所有点到(n,n)的最短距离
{priority_queue<Node> que;que.push(Node(n , n , grid[n][n]));dist[n][n] = grid[n][n];while(!que.empty()){Node now = que.top();que.pop();for(int i = 0;i < 4;i++){int x = now.x + dir[i][0];int y = now.y + dir[i][1];if(!cango(x , y)) continue;if(dist[x][y] > dist[now.x][now.y] + grid[x][y]){dist[x][y] = dist[now.x][now.y] + grid[x][y];que.push(Node(x , y , dist[x][y]));}}}
}LL DP(int x , int y)
{if(x == n && y == n) return dp[n][n] = 1;if(dp[x][y] != -1) return dp[x][y];LL sum = 0;for(int i = 0;i < 4;i++){int nx = x + dir[i][0];int ny = y + dir[i][1];if(!cango(nx , ny)) continue;if(dist[x][y] > dist[nx][ny])//选择B区域sum += DP(nx , ny);//不能写成dp[x][y] += DP(nx , ny);!!!!}return dp[x][y] = sum;
}int main()
{while(scanf("%d",&n) != EOF){int i , j;memset(dp , -1 , sizeof(dp));for(i = 1;i <= n;i++)for(j = 1;j <= n;j++){scanf("%d",&grid[i][j]);dist[i][j] = inf;}bfs();cout << DP(1,1) << endl;}return 0;
}这篇关于HDU 1428 漫步校园 （搜索 + dp）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
