搜尋 Find a way HDU - 2612 BFS

搜尋 Find a way HDU - 2612 BFS

題意：

兩個人Y和M要去同一家肯德基吃飯，然後問你怎麼走所花費的總時間最少。

‘#’代表的是牆不能走。

思路：

就是廣搜開兩個數組，雖然在同一個隊列裡面，但是标記一下之後更新與他相關的相關數組就可以了。我wa了幾次，最後一定要注意 有可能以有一家kfc是被包圍在牆壁裡面的不可能到達，是以要對可以到達的kfc做一下标記。

其餘就是bfs的闆子套一下就可以了。

最後輸出的是兩個人到達同一家店的時間總和。記得乘11啊。

ac代碼：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
char map[205][205];
int dis1[205][205];     //dis1和vis1處理的是Y走的情況
int vis1[205][205];
int dis2[205][205];     //dis2和vis2處理的是M走的情況
int vis2[205][205];
int map1[205][205];     //用來标記這家kfc到底能不能到
int go[8]={1,0,-1,0,0,1,0,-1};
struct node{
    int x,y,v;          //v可以用來表示這個節點現在是誰在走1代表Y  2代表M。
};
queue<node>q;
void bfs(int nn,int mm){
    node now,temp;
    while(!q.empty()){
        //cout<<45<<endl;
        now=q.front();
        q.pop();
        if(map[now.x][now.y]=='@'){
            map1[now.x][now.y]=1;
        }
        for(int i=0;i<8;i+=2){
            int xx=now.x+go[i];
            int yy=now.y+go[i+1];
            if(xx>=1&&xx<=nn&&yy>=1&&yy<=mm&&map[xx][yy]!='#'){
                if(now.v==1&&!vis1[xx][yy]){
                    dis1[xx][yy]=dis1[now.x][now.y]+1;
                    temp.x=xx;temp.y=yy;temp.v=1;
                    q.push(temp);
                    vis1[xx][yy]=1;
                }
                if(now.v==2&&!vis2[xx][yy]){
                    dis2[xx][yy]=dis2[now.x][now.y]+1;
                    temp.x=xx;temp.y=yy;temp.v=2;
                    q.push(temp);
                    vis2[xx][yy]=1;
                }
            }
        }
    }
    return ;
}
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        while(!q.empty())q.pop();
        memset(dis1,0,sizeof(dis1));
        memset(dis2,0,sizeof(dis2));
        memset(vis1,0,sizeof(vis1));
        memset(vis2,0,sizeof(vis2));
        memset(map1,0,sizeof(map1));
        for(int i=1;i<=n;i++){
            scanf("%s",map[i]+1);
        }
        node Y,M;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(map[i][j]=='Y'){
                    Y.x=i;Y.y=j;Y.v=1;
                    vis1[i][j]=1;
                    q.push(Y);
                }
                if(map[i][j]=='M'){
                    M.x=i;M.y=j;M.v=2;
                    vis2[i][j]=1;
                    q.push(M);
                }
            }
        }
        bfs(n,m);
        int minn=0x3fffffff;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(map1[i][j]&&map[i][j]=='@'&&dis1[i][j]+dis2[i][j]<=minn){ //記得判斷能不能到
                    //cout<<dis1[i][j]<<" "<<dis2[i][j]<<endl;
                    minn=dis1[i][j]+dis2[i][j];
                }
            }
        }
        printf("%d\n",minn*11);
    }
    return 0;
}