首先從終點bfs，保存每一個節(jié)點到終點的最短路徑，然后從起點dfs，記憶化，如果滿足題目給定的拓?fù)湫蚓图由蠌哪莻€點到終點的路徑數(shù)。所謂滿足拓?fù)湫蚓褪穷}目所給定的taking a path from A to B to be progress if there exists a route from B to his home that is shorter than any possible route from A，這句話仔細(xì)讀上幾十遍就能明白題目意圖了。
漫步校園
代碼：
#include <iostream>
#include <queue>
using namespace std;
int dir[4][2] = 
{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
struct point {
int x;
int y;
int time;
bool friend operator < (point a, point b) {
return a.time > b.time;
}
}temp, tt;
priority_queue < point > q;
int hash[51][51], map[51][51];
__int64 dp[51][51];
int n;
__int64 dfs(int x, int y) {
int i;
int tx, ty;
__int64 sum = 0;
if(x == n && y == n)
return 1;
for(i = 0; i < 4; i++) {
tx = x + dir[i][0];
ty = y + dir[i][1];
if(tx < 1 || ty < 1 || tx > n || ty > n)
continue;
if(hash[x][y] > hash[tx][ty]) {
if(dp[tx][ty] == -1) {
dp[tx][ty] = dfs(tx, ty);
}
sum += dp[tx][ty];
}
}
return sum;
}
int main() {
int i, j;
while(scanf("%d", &n) != EOF) {
for(i = 1; i <= n; i++) {
for(j = 1; j <= n; j++) {
scanf("%d", &map[i][j]);
}
}
temp.x = n;
temp.y = n;
temp.time = map[n][n];
memset(hash, -1, sizeof(hash));
hash[n][n] = map[n][n];
while(!q.empty())
q.pop();
q.push( temp );
while(!q.empty()) {
temp = q.top();
q.pop();
for(i = 0; i < 4; i++) {
tt.x = temp.x + dir[i][0];
tt.y = temp.y + dir[i][1];
if(tt.x < 1 || tt.y < 1 || tt.x > n || tt.y > n)
continue;
tt.time = temp.time + map[tt.x][tt.y];
if(hash[ tt.x ][ tt.y ] == -1 || tt.time < hash[ tt.x ][ tt.y ]) {
hash[ tt.x ][ tt.y ] = tt.time;
q.push( tt );
}
}
}
memset(dp, -1, sizeof(dp));
dp[1][1] = dfs(1, 1);
printf("%I64d\n", dp[1][1]);
}
return 0;
}