HDU1248 漫步校园(记忆化搜索，spfa)

题目链接。

分析：

他考虑从A区域到B区域仅当存在一条从B到机房的路线比任何一条从A到机房的路线更近(否则可能永远都到不了机房了…)。

这句话是本题的关键。我WA了很多次。。也是因为没有看懂该话。

本题思路就是先用spfa求出(n,n)到各点的最短路，然后用记忆化搜索。

AC代码如下：

#include <stdio.h>

#define MAXN 55

const int INF = (1<<24);
const int MAX_QUE = MAXN*MAXN;

typedef struct Pos{
    int x, y;
}Pos;

Pos q[MAXN*MAXN];
int G[MAXN][MAXN], d[MAXN][MAXN], n, vis[MAXN][MAXN];
__int64 path[MAXN][MAXN];

int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};

void spfa(){
    Pos pos, npos;
    int i, j, front, rear, di;
    front = rear = 0;
    for(i=1; i<=n; i++){
        for(j=1; j<=n; j++){
            d[i][j] = INF;
            vis[i][j] = 0;
        }
    }
    pos.x = n; pos.y =n;
    d[n][n] = G[n][n];
    vis[n][n] = 1;
    q[rear++] = pos;
    while(front != rear){
        pos = q[front++];
        front %= MAX_QUE;
        vis[pos.x][pos.y] = 0;
        for(di=0; di<4; di++){
            npos.x = pos.x+dx[di];
            npos.y = pos.y+dy[di];
            if(npos.x>=1 && npos.x<=n && npos.y>=1 && npos.y<=n){
                if(d[npos.x][npos.y] > d[pos.x][pos.y]+G[npos.x][npos.y]){
                    d[npos.x][npos.y] = d[pos.x][pos.y]+G[npos.x][npos.y];
                    if(!vis[npos.x][npos.y]){
                        vis[npos.x][npos.y] = 1;
                        q[rear++] = npos;
                        rear %= MAX_QUE;
                    }
                }
            }
        }
    }
}

__int64 dfs(int x, int y){  //记忆化搜索
    if(x == n && y == n) return 1;
    if(path[x][y] >= 0) return path[x][y];
    __int64 sum = 0;
    int di, nx, ny;
    for(di=0; di<4; di++){
        nx = x+dx[di]; ny = y+dy[di];
        if(nx<1 || nx>n || ny<1 || ny>n || vis[nx][ny]) continue;
        if(d[nx][ny]>=d[x][y]) continue;
        sum += dfs(nx, ny);
    }
    path[x][y] = sum;
    return sum;
}

int main(){
    int i, j;
    while(scanf("%d", &n) == 1){
        for(i=1; i<=n; i++){
            for(j=1; j<=n; j++){
                scanf("%d", &G[i][j]);
            }
        }

        spfa();

        for(i=1; i<=n; i++){
            for(j=1; j<=n; j++){
                path[i][j] = -1;
                vis[i][j] = 0;
            }
        }


        printf("%I64d\n", dfs(1,1));
    }

    return 0;
}