小A与小B

BFS

这道题要求小A和小B最早的相遇时间。
而小A的行走规则是：每次可以走8个方向，每次走一步
小B的行走规则是：每次可以走4个方向，但每次走两步（两步不一定是要同方向）

于是我们可以在每秒分别在对小A，小B每秒的行走进行讨论：
分别建立小A，小B的队列，依次对他俩进行，并分别记录下行走中可以到达的点，若其中一人目前走到的点是另一人曾经走过的，则说明他们俩必定相遇，根据的性质，当前时间一定是最优解。

注意：

• 在传统里，while的结束条件是队列为空（q.size()或者!q.empty()），但在此题中，是对每秒的情况进行讨论，所以结束条件是当前之前的队列元素全部讨论过一次，即设循环只需执行这次前的q.size()次即可。
• 在对每秒的情况进行讨论时，若小A，小B已相遇，则可以跳出循环输出，若未相遇，则讨论到小A，小B都走不动为止，有一个人还能走，就继续。

#include<bits/stdc++.h>//0->A 1->B
using namespace std;
const int dx[]={1,0,-1,0,1,1,-1,-1};
const int dy[]={0,1,0,-1,1,-1,1,-1};
int n,m;
char a[1005][1005];
bool vis[2][1005][1005];
struct node{
    int x,y;
};
queue<node> q[2];
bool check_bfs(int w){
    int Size=q[w].size();
    while(Size--){
        int x=q[w].front().x;
        int y=q[w].front().y;
        q[w].pop();
        for(int k=0;k<(w?4:8);k++){
            int tx=x+dx[k];
            int ty=y+dy[k];
            if(tx<1 || tx>n || ty<1 || ty>m || a[tx][ty]=='#' || vis[w][tx][ty]) continue;
            if(vis[w^1][tx][ty]) return true;
            q[w].push((node){tx,ty});
            vis[w][tx][ty]=1;
        }
    }
    return false;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            if(a[i][j]=='C'){
                q[0].push((node){i,j});
                vis[0][i][j]=1;
            }
            if(a[i][j]=='D'){
                q[1].push((node){i,j});
                vis[1][i][j]=1;
            }
        }
    }
    int tim=0;
    bool flag=false;
    while(q[0].size() || q[1].size()){
        flag=false;
        tim++;
        if(q[0].size() && check_bfs(0)){
            flag=true;
            break;
        }
        if(q[1].size() && check_bfs(1)){
            flag=true;
            break;
        }
        if(q[1].size() && check_bfs(1)){
            flag=true;
            break;
        }
    }
    if(flag){
        puts("YES");
        cout<<tim<<'\n';
    }
    else{
        puts("NO");
    }
    return 0;
}