【每一】双BFS板子

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

这题属于双BFS模板题
A一个队列进行BFS B一个队列进行BFS
两者同时进行BFS----B走两步 A走一步
BFS过程中判断A是否走到了B走过的点（vis数组判断即可）
即：

while(!que[0].empty()||!que[1].empty())
    {
        ans++;
        //0-B B每次可以走两步
        if(bfs(0)) break;
        if(bfs(0)) break;
        if(bfs(1)) break;
    }

AC：

//OK
#include<bits/stdc++.h>
using namespace std;

struct node
{
    int x,y;
}point;
queue<node> que[2];
int ans=0,N,M,dx[]={0,0,1,-1,1,1,-1,-1},dy[]={1,-1,0,0,1,-1,1,-1};
char maze[1005][1005];
bool metAble=0,vis[2][1005][1005]={0};
bool bfs(bool a)
{
    int i,x,y,q=que[a].size();
    while(q--)
    {
        front=que[a].front(),que[a].pop();
        int dir=a?8:4;
        for(i=0;i<dir;i++){
            x=front.x+dx[i],y=front.y+dy[i];
            if(x<0||x>=N||y<0||y>=M||maze[x][y]=='#'||vis[a][x][y])continue;
            if(vis[!a][x][y])return metAble=1; // 遇到对方走的点
            vis[a][x][y]=1;
            point.x=x,point.y=y,que[a].push(point);
        }
    }
    return 0;
}
int main()
{
    int i,j,x1,y1,x2,y2;
    scanf("%d%d",&N,&M);
    for(i=0;i<N;i++)
        for(j=0;j<M;j++)
        {
            scanf(" %c",&maze[i][j]);
            if(maze[i][j]=='D')x1=i,y1=j;
            if(maze[i][j]=='C')x2=i,y2=j;
        }

    point.x=x1,point.y=y1,vis[0][x1][y1]=1,que[0].push(point);
    point.x=x2,point.y=y2,vis[1][x2][y2]=1,que[1].push(point);
    while(!que[0].empty()||!que[1].empty())
    {
        ans++;
        //0-B B每次可以走两步
        if(bfs(0))break;
        if(bfs(0))break;
        if(bfs(1))break;
    }
    if(metAble) printf("YES\n%d\n",ans);
    else printf("NO\n");
    return 0;
}