小A与小B

题意:走迷宫,问能不能碰头,能的话,什么时候碰头
题解:广搜,定义一个时间戳,分别把两个开始点能走到的点的时间戳+1,然后把这些能走到的点,的能走到的点的时间戳+2......(已经走过的点不能再往回走)
如果最后队列为空,仍没有可以重合的点,输出NO
否则输出YES,合最开始重合的时间戳

#include<bits/stdc++.h>
using namespace std;
struct qw
{
    int x,y;
}t;
int n,m,vis[2][1005][1005],step=0;
char a[1005][1005];
queue<qw> q[2];
int dx[]={0,0,1,-1,1,1,-1,-1},dy[]={1,-1,0,0,1,-1,1,-1};
void bfs(int w)
{
    int len=q[w].size();
    while(len--)
    {
        t=q[w].front();q[w].pop();
        for(int i=0;i<4+(w==0?4:0);i++)
        {
            int bx=t.x+dx[i],by=t.y+dy[i];
            if(bx>n||bx<1||by>m||by<1||vis[w][bx][by]||a[bx][by]=='#') continue;
            vis[w][bx][by]=1;q[w].push((qw){bx,by});
            if(vis[w^1][bx][by]) {cout<<"YES"<<endl<<step<<endl;exit(0);}
        }
    }
}
void solve()
{
    while(step<=n*m)
    {
        step++;//时间戳
        bfs(0);//小A走8个方向
        bfs(1);//小B连续走两次
        bfs(1);
    }
    cout<<"NO"<<endl;
}
int main()
{
    ios::sync_with_stdio(false);
    int i,j;
    cin>>n>>m;
    for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
    {
        cin>>a[i][j];
        if(a[i][j]=='C') q[0].push((qw){i,j}),vis[0][i][j]=1;
        if(a[i][j]=='D') q[1].push((qw){i,j}),vis[1][i][j]=1;
    }
    solve();
}