程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 1428 漫步校園(記憶化搜索)

HDU 1428 漫步校園(記憶化搜索)

編輯：C++入門知識

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
******************************************************************************************************************************

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

題目要求問左上角走到右下角有多少條路，要求如題目描述的A區域到B區域最短距離。題目主要地方已在上面描紅。

方法：記憶化搜索(BFS+DFS+狀態記錄)

代碼：
[cpp]
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define LL __int64

using namespace std;

LL n,tot;
LL Map[55][55],vis[55][55];//圖，每一點的狀態(有多少條路)
LL dis[55][55];//終點到各點的最短距離
LL dir[][2]={{0,-1},{-1,0},{1,0},{0,1}};//方向

struct Node{
    int x,y,step;
};

queue<Node>que;//隊列

void bfs(){//寬搜，確定終點到各點距離
    Node now,next;
    int i,j;
    now.x=n,now.y=n,now.step=0,tot=0;
    que.push(now);
    dis[n][n]=Map[n][n];
    while(!que.empty()){
        now=que.front(),que.pop();
        for(i=0;i<4;i++){
            next.x=now.x+dir[i][0],next.y=now.y+dir[i][1],next.step=now.step+1;
            if(next.x<1||next.y<1||next.x>n||next.y>n) continue;
            if(dis[next.x][next.y]>dis[now.x][now.y]+Map[next.x][next.y]||dis[next.x][next.y]==-1){
                dis[next.x][next.y]=dis[now.x][now.y]+Map[next.x][next.y];
                que.push(next);
            }
        }
    }
}

LL dfs(LL x,LL y){//深搜，確定有多少條路可到達
    int sx,sy,i;
    if(vis[x][y]) return vis[x][y];//路已經走過，返回這點已經有的值(記憶化搜索)
    if(x==n&&y==n){//能夠到達終點，多一條路，return 1;
        return 1;
    }
    for(i=0;i<4;i++){
        sx=x+dir[i][0],sy=y+dir[i][1];
        if(sx>n||sy>n||sx<1||sy<1) continue;
        if(dis[sx][sy]>=dis[x][y]) continue;//題目要求選短的路
        vis[x][y]+=dfs(sx,sy);
    }
    return vis[x][y];
}
//主函數
int main(){
    LL i,j;
    while(~scanf("%I64d",&n)){
        for(i=1;i<=n;i++)
        for(j=1;j<=n;j++) scanf("%I64d",&Map[i][j]);
        memset(dis,-1,sizeof(dis));
        memset(vis,0,sizeof(vis));
        bfs();
        dfs(1,1);
        printf("%I64d\n",vis[1][1]);//記憶化搜索，從終點返回，所以是vis[1][1]
    }
    return 0;
}

特別地，記憶化搜索在什麼地方體現出來呢，
在DFS中，如果把DFS不使用記憶化搜索而改成如下代碼(普通深搜)：
[cpp]
void dfs(int x,int y){
    int sx,sy,i;
    if(x==n&&y==n){
        tot++;//tot記錄能夠到達終點的路的條數
        return;
    }
    for(i=2;i<4;i++){
        sx=x+dir[i][0],sy=y+dir[i][1];
        if(sx>n||sy>n) continue;
        if(dis[sx][sy]>=dis[x][y]) continue;
        dfs(sx,sy);
    }
}

這樣伱就掛了！！TLE，MLE。

再看一張圖，苊對記憶化搜索的最基礎的理解：