hdu 2102 A計劃 詳細題解 （BFS+優先隊列）

這道題屬於BFS+優先隊列

開始看到四分之一的AC率感覺有點嚇人，後來一做感覺就是模板改了點東西而已，一遍就AC了，不過在主函數和全局變量裡面都定義了n和m導致我白白浪費了debug的時間。果然全局變量得小心用啊。

跟模板一樣的，定義一個結構體，只不過多加了個參數，就是迷宮的層數，我用0代表第一層，1代表第二層，這在數組裡面會體現的。

struct node {
    int index;//層數
    int x,y;//坐標
    int time;
    friend bool operator <(const node &a,const node &b){
    //時間少的放在隊列前面
        return a.time>b.time;
    }
};

我定義的那個map是

char map[2][11][11];

map[層數][x][y]這樣的。

還有個can_go 函數檢測當前點是否可走：

int can_go(int index,int x,int y){
   if(x<0||x>=n||y<0||y>=m||map[index][x][y]=='*'){
    return 0;
   }
   return 1;
}

我大概就講一下跟模板題有啥不同吧。

這道題裡面會遇到傳送門’#’只要遇到就把當前層格子標記為已經過vis[index][x][y]=1之後立馬飛到另一層就行了，注意，若另一層是牆那就掛了，說明這裡不能走，直接continue換個方向繼續，或者另一層同一位置也是傳送門’#’那也不行，也continue就行了

if(map[!next.index][next.x][next.y]=='*'||
	map[!next.index][next.x][next.y]=='#'){
	continue;
}

之後只要隊列不為空，就取出隊列的頭節點，判斷是否為終點，如果是，則返回到達當前節點所需時間即:now.time；若不是，那接下來把now的四個方向全部遍歷一遍。如果遍歷到達不是牆就將其加入隊列，並且把當前time更新：next.time=now.time+1。一直循環直到que.top出來的坐標代表的是終點為止。

貼個代碼：

#include 
#include 
#include 
#include 

using namespace std;

char map[2][11][11];
int vis[2][11][11];
int t,n,m;
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};

struct node {
    int index;//層數
    int x,y;//坐標
    int time;
    friend bool operator <(const node &a,const node &b){
    //時間少的放在隊列前面
        return a.time>b.time;
    }
};

int can_go(int index,int x,int y){
   if(x<0||x>=n||y<0||y>=m||map[index][x][y]=='*'){
    return 0;
   }
   return 1;
}

//bfs若time > T 則返回 -1
int bfs(int index,int x,int y){
    priority_queueque;
    int i;
    node now,next;
    memset(vis,0,sizeof(vis));

    now.index=index;
    now.x=x;
    now.y=y;
    now.time=0;

    vis[index][x][y]=1;
    que.push(now);
    while(!que.empty()){
        now=que.top();
        que.pop();
        if(now.time>t){
            return -1;
        }
        if(map[now.index][now.x][now.y]=='P'){
            return 1;
        }
        for(i=0;i<4;i++){
            next.index=now.index;
            next.x=now.x+dir[i][0];
            next.y=now.y+dir[i][1];
            if(!vis[next.index][next.x][next.y] && can_go(next.index,next.x,next.y)){
                vis[next.index][next.x][next.y]=1;
                if(map[next.index][next.x][next.y]=='#'&&!vis[!next.index][next.x][next.y]){


                    if(map[!next.index][next.x][next.y]=='*'||
                       map[!next.index][next.x][next.y]=='#'){
                        continue;
                    }
                    next.index=!next.index;
                    vis[next.index][next.x][next.y]=1;
                    next.time=now.time+1;
                    que.push(next);
                }
                else {
                    next.time=now.time+1;

                    que.push(next);
                }
            }
        }
    }
    return -1;
}

int main()
{
    int ans;
    int i;
    int c;
    scanf(%d,&c);
    while(c--){
        scanf(%d%d%d,&n,&m,&t);
        //printf(%d%d%d,n,m,t);
        for(i=0;i