小A与小B

题目描述

小A与小B这次两个人都被困在了迷宫里面的两个不同的位置，而他们希望能够迅速找到对方，然后再考虑如何逃离迷宫的事情。小A每次可以移动一个位置，而小B每次可以移动两次位置，小A移动的方向是上下左右左上左下右上右下8个方向，小B移动的方向是上下左右4个方向，请问他们最早什么时候能够找到对方，如果他们最终无法相遇，那么就输出”NO"。

输入描述:

第一行两个整数N，M分别表示迷宫的行和列。接下来一个N×M的矩阵其中"C"表示小A的位置,"D"表示小B的的位置，"＃"表示不可通过的障碍，"."则是可以正常通过的位置。字符用空格隔开第一行两个整数N，M分别表示迷宫的行和列。接下来一个N×M的矩阵其中"C"表示小A的位置,"D"表示小B的的位置，"＃"表示不可通过的障碍，"."则是可以正常通过的位置。字符用空格隔开

输出描述:

如果可以相遇，第一行输出一个YES，第二行一个整数输出最短的相遇时间。
否则就输出一个NO表示不能相遇。

题解

看到输出相遇的最短时间以及走迷宫的背景，很容易想到BFS。而跟普通BFS不相同的一点是这道题有两个人在同时走，那我们就同时对两个人进行BFS，看两人在何时可以遇到。

bfs函数代码详解

在代码实现中，我们用0表示小B（走两步的），1表示走1步的

bool bfs(int sign){//sign表示是哪个人在走
    int q=Q[sign].size();//用q来记录当前步我们需要处理多少多少
    //千万不能直接写!Q[sign].empty(),那样便会一直走下去
    while(q--){
        node now=Q[sign].front();
        Q[sign].pop();
        for(int i=0;i<4+(sign==1?4:0);i++){//判断是走四步还是走八步
            int fx=now.x+dir[i][0];
            int fy=now.y+dir[i][1];
            if(fx>=0&&fx<n&&fy>=0&&fy<m&&mp[fx][fy]!=&#39;#&#39;&&!vis[sign][fx][fy]){
                if(vis[1-sign][fx][fy])return flag=true;
                //对方这一步走过，即相遇了 返回true
                vis[sign][fx][fy]=1;
                Q[sign].push({fx,fy});
            }
        }
    }
    return false;
}

大体上还是BFS框架，如果对BFS理解比较好的话应该比较好懂的，唯一要注意的一点就是每次我们处理的都是单步

完整代码

#include<bits/stdc++.h>
using namespace std;
 struct node{
    int x,y;
};
queue<node>Q[2];
int n,m,x,y,xx,yy;
int dir[8][2]={0,1,0,-1,1,0,-1,0,1,1,1,-1,-1,1,-1,-1};
char mp[1005][1005];
bool flag=false,vis[2][1005][1005]={0};
int ans=0;
bool bfs(int sign){
    int q=Q[sign].size();
    while(q--){
        node now=Q[sign].front();
        Q[sign].pop();
        for(int i=0;i<4+(sign==1?4:0);i++){
            int fx=now.x+dir[i][0];
            int fy=now.y+dir[i][1];
            if(fx>=0&&fx<n&&fy>=0&&fy<m&&mp[fx][fy]!=&#39;#&#39;&&!vis[sign][fx][fy]){
                if(vis[1-sign][fx][fy])return flag=true;
                vis[sign][fx][fy]=1;
                Q[sign].push({fx,fy});
            }
        }
    }
    return false;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            scanf(" %c",&mp[i][j]);
            if(mp[i][j]==&#39;D&#39;)x=i,y=j;
            else if(mp[i][j]==&#39;C&#39;)xx=i,yy=j;
        }
    }
    Q[0].push({x,y});Q[1].push({xx,yy});
    while(!Q[0].empty()||!Q[1].empty()){
        ans++;
        if(bfs(0))break;
        if(bfs(0))break;
        if(bfs(1))break;
    }
    if(flag)printf("YES\n%d\n",ans);
    else printf("NO\n");
}