HDU 1428 漫步校園（最短路+記憶化搜尋）

漫步校園

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 3991    Accepted Submission(s): 1235

Problem Description LL最近沉迷于AC不能自拔，每天寝室、機房兩點一線。由于長時間坐在電腦邊，缺乏運動。他決定充分利用每次從寝室到機房的時間，在校園裡散散步。整個HDU校園呈方形布局，可劃分為n*n個小方格，代表各個區域。例如LL居住的18号宿舍位于校園的西北角，即方格(1,1)代表的地方，而機房所在的第三實驗樓處于東南端的(n,n)。因有多條路線可以選擇，LL希望每次的散步路線都不一樣。另外，他考慮從A區域到B區域僅當存在一條從B到機房的路線比任何一條從A到機房的路線更近(否則可能永遠都到不了機房了…)。現在他想知道的是，所有滿足要求的路線一共有多少條。你能告訴他嗎?

Input 每組測試資料的第一行為n(2=<n<=50)，接下來的n行每行有n個數，代表經過每個區域所花的時間t(0<t<=50)(由于寝室與機房均在三樓，故起點與終點也得費時)。

Output 針對每組測試資料，輸出總的路線數(小于2^63)。

Sample Input

3
1 2 3
1 2 3
1 2 3
3
1 1 1
1 1 1
1 1 1
        

Sample Output

1
6
        

Author LL  

Source ACM暑期集訓隊練習賽（三）

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

題目是中文的，沒有什麼好說的，一看就知道是要記憶化搜尋，但是每個點到終點的最短距離不好求，題目中隻給了鄰接矩陣，是以采用了BFS求每個點到終點的最短路徑，具體看代碼，剩下的就是記憶化搜尋了。 有一點要注意一下，最後的結果是2^63，是以結果要用__int64，函數的傳回值也是！！

AC代碼：

#include <iostream>
#include <cstring>
#include <queue>
#include<stdio.h>
using namespace std;
int a[55][55];
__int64 dp[55][55];
int n;
int dis[55][55];
const int INF=0x3f3f3f3f;
int dir[4][2]= {1,0,0,1,-1,0,0,-1};
struct node
{
    int x,y;
};
bool OK(int x,int y)
{
    if(x<0||x>=n||y<0||y>=n)
        return false;
    return true;
}
void BFS()
{
    queue<node>q;
    node now,next;
    now.x=n-1;
    now.y=n-1;
    //memset(dis,INF,sizeof(dis));
    dis[n-1][n-1]=a[n-1][n-1];
    q.push(now);
    while(!q.empty())
    {
        now=q.front();
        q.pop();
        for(int i=0; i<4; i++)
        {
            next.x=now.x+dir[i][0];
            next.y=now.y+dir[i][1];
            if(OK(next.x,next.y))
            {
                if(dis[now.x][now.y]+a[next.x][next.y]<dis[next.x][next.y])
                {
                    dis[next.x][next.y]=dis[now.x][now.y]+a[next.x][next.y];
                    q.push(next);
                }
            }
        }
    }
}
__int64 DFS(int x,int y)
{
    if(dp[x][y]>0) return dp[x][y];
    for(int i=0; i<4; i++)
    {
        int xx=x+dir[i][0];
        int yy=y+dir[i][1];
        if(OK(xx,yy)&&dis[xx][yy]<dis[x][y])
        {
            dp[x][y]+=DFS(xx,yy);
        }
    }
    return dp[x][y];
}
int main()
{
    while(cin>>n)
    {
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
            {
                cin>>a[i][j];
                dis[i][j]=INF;
            }
        BFS();
        memset(dp,0,sizeof(dp));
        dp[n-1][n-1]=1;
        DFS(0,0);
        //cout<<dp[0][0]<<endl;
        printf("%I64d\n",dp[0][0]);
    }
    return 0;
}