HDOJ 1428 漫步校園

題目連結：http://acm.hdu.edu.cn/showproblem.php?pid=1428

這道題目應該是一道裸的記憶化搜尋，但不知道為什麼HDOJ官方分類裡面把它分進了Dynamic Programming(動态規劃)裡面

，這題雖然是中文題，但是其實還是有很多童鞋讀不懂這道題的題意，尤其是這句話：

考慮從A區域到B區域僅當存在一條從B到機房的路線比任何一條從A到機房的路線更近

這句話說的有點玄啊，意思其實就是如果我們目前位置到終點的最短路徑比下一個點的最短路徑小，那就不走這個點，也就是說我們還需要求出每一個點到終點的最短路徑，在将其作為值進行一次從起點開始的記憶化搜尋，即可找到我們的答案。

#include <iostream>
#include <queue>
#include <cstring>
#include <cstdio>
using namespace std;
const int MAXN = 55;
const int INF = 0x3f3f3f3f;
int map[MAXN][MAXN];
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
struct Node
{
    int x,y;
};
int dis[MAXN][MAXN];
__int64 res[MAXN][MAXN];
bool vis[MAXN][MAXN];
int n; 
void SPFA()
{
    queue<Node> Q;
    int i,j,k;
    for(i = 0;i < MAXN;i ++)
        for(j = 0;j < MAXN;j ++)
            dis[i][j] = INF;
    memset(vis,0,sizeof(vis));
    dis[n][n] = map[n][n];
    Node p,q;
    p.x = n;
    p.y = n;
    Q.push(p);
    vis[p.x][p.y] = 1;
    while(!Q.empty())
    {
        q = Q.front();
        Q.pop();
        vis[q.x][q.y] = 0;
        for( k = 0;k < 4;k ++)
        {
            p.x = q.x + dir[k][0];
            p.y = q.y + dir[k][1];
            if(p.x >= 1 && p.x <= n && p.y >= 1 && p.y <= n && dis[p.x][p.y] > dis[q.x][q.y] + map[p.x][p.y])
            {
                dis[p.x][p.y] = dis[q.x][q.y] + map[p.x][p.y];
                if(!vis[p.x][p.y])
                {
                    Q.push(p);
                    vis[p.x][p.y] = 1;
                }
            }
        }
    }
}
__int64 dfs(int i,int j)
{
    if(i == n && j == n) return 1;
    if(res[i][j] != -1) return res[i][j];
    res[i][j] = 0;
    int k;
    for(k = 0;k < 4;k ++)
    {
        int x,y;
        x = i + dir[k][0];
        y = j + dir[k][1];
        if(x >= 1 && x <= n && y >= 1 && y <= n && dis[x][y] < dis[i][j])
            res[i][j] += dfs(x,y);
    }
    return res[i][j];
}
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]);
        SPFA();
        memset(res,-1,sizeof(res));
        printf("%I64d\n",dfs(1,1));
    }
    return 0;
}