https://ac.nowcoder.com/acm/problem/23486

题意：

有一迷宫，小A每秒移动1次，方向为上下左右左上左下右上右下8个方向，小B每秒移动2次，方向为上下左右四个方向，问他们最早什么时候能够相遇？

分析：

迷宫问题，求最短相遇时间，优先考虑用bfs。因为小B每秒运动2次，所以我们可以给他每秒进行两次bfs，注意一下，bfs里面要判断一下是A还是B，小A是8个方向的，小B是4个方向的，用vis[0][x][y]和vis[1][x][y]分别记录走过的路径。
bfs：当小A走的时候，广搜周围路径，如果该点被小B所走过的时候，说明他们相遇了，答案出来了。

代码：

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#include<queue>
#include<iostream>
using namespace std;
typedef long long ll;
int i,j,n,k,m,t,s,y;
int ans,flag=1;
struct Hi{
    int x,y;
};
queue<Hi>q1,q2;//小B。小A
char a[1005][1005];
int vis[2][1005][1005];//0代表小B，1代表小A
int xx[]={0,0,1,-1,1,1,-1,-1},yy[]={1,-1,0,0,1,-1,1,-1};
bool bfs(int k){//0代表小A，1代表小B
    int t;
    if(k==1){//小B
        t=q1.size();
        while(t--){
            Hi f=q1.front();
            vis[0][f.x][f.y]=1;
            q1.pop();
            for(int i=0;i<4;i++){
                int dx=xx[i]+f.x;
                int dy=yy[i]+f.y;
                if(dx<0||dx>=n||dy<0||dy>=m||a[dx][dy]=='#'||vis[0][dx][dy])   continue;//此路不通
                if(vis[1][dx][dy]) return flag=1;//找到对方了
                vis[0][dx][dy]=1;//标记走过
                q1.push((Hi){dx,dy});
            }
        }
        return 0;//没碰到对方
    }else{//把上面复制下来改一下就行了
        t=q2.size();
        while(t--){
            Hi f=q2.front();
            vis[1][f.x][f.y]=1;
            q2.pop();
            for(int i=0;i<8;i++){
                int dx=xx[i]+f.x;
                int dy=yy[i]+f.y;
                if(dx<0||dx>=n||dy<0||dy>=m||a[dx][dy]=='#'||vis[1][dx][dy])   continue;//此路不通
                if(vis[0][dx][dy]) return flag=1;//找到对方了
                vis[1][dx][dy]=1;//标记走过
                q2.push((Hi){dx,dy});
            }
        }
        return 0;//没碰到对方
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    getchar();
    for(i=0;i<n;i++){
        for(j=0;j<m;j++){
            cin>>a[i][j];
            if(a[i][j]=='C'){
                q2.push((Hi){i,j});
                vis[1][i][j]=1;
            }
            else if(a[i][j]=='D'){
                q1.push((Hi){i,j});
                vis[0][i][j]=1;
            }
        }
    }
    while(!q1.empty() || !q2.empty()){
        ans++;
        if(bfs(0))  break;
        if(bfs(1))  break;//找到了
        if(bfs(1))  break;//小B一秒走2次

    }
    if(flag){
        printf("YES\n");
        printf("%d",ans);
    }else{
        printf("NO\n");
    }
}