牛客——小A与小B （双向广搜）

题意：

迷宫，小A每次可以移动一个位置，而小B每次可以移动两次位置，小A移动的方向是上下左右左上左下右上右下8个方向，小B移动的方向是上下左右4个方向，请问他们最早什么时候能够找到对方，如果他们最终无法相遇，那么就输出”NO"。

思路：

双向广搜经典问题

将A和B的起始位置都加到队列里，同时跑BFS，判断走过的位置是否已经被对方走过，如果走过的话，说明已经相遇了，输出即可。

要注意A和B走的方向和步数不一样。

代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>PII;
#define I_int ll
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
char F[200];
inline void out(I_int x) {
    if (x == 0) return (void) (putchar('0'));
    I_int tmp = x > 0 ? x : -x;
    if (x < 0) putchar('-');
    int cnt = 0;
    while (tmp > 0) {
        F[cnt++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (cnt > 0) putchar(F[--cnt]);
    cout<<endl;
}

const int maxn=1100;

char mp[maxn][maxn];
struct node{
    int x,y;
};
queue<node>q[2];
int vis[2][maxn][maxn];
int n,m;
int sx,sy,ex,ey;
int nx[] = {1, -1, 0, 0, 1, -1, -1, 1};
int ny[] = {0, 0, 1, -1, -1, 1, -1, 1};
bool bfs(int u){
    int tt=q[u].size();
    while(tt--){
        node t=q[u].front();
        q[u].pop();
        if(u==0){
            for(int i=0;i<8;i++){
                int xx=t.x+nx[i],yy=t.y+ny[i];
                if(xx<1||yy<1||xx>n||yy>m||mp[xx][yy]=='#')
                    continue;
                if(!vis[u][xx][yy]){
                    if(vis[u^1][xx][yy])    return true;
                    vis[u][xx][yy] = 1;
                    q[u].push({xx,yy});
                }
            }
        }
        else{
            for(int i=0;i<4;i++){
                int xx=t.x+nx[i],yy=t.y+ny[i];
                if(xx<1||yy<1||xx>n||yy>m||mp[xx][yy]=='#')
                    continue;
                if(!vis[u][xx][yy]){
                    if(vis[u^1][xx][yy])    return true;
                    vis[u][xx][yy] = 1;
                    q[u].push({xx,yy});
                }
            }
        }
    }
    return 0;
}

int sol(){
    int res=0;
    vis[0][sx][sy]=1;vis[1][ex][ey]=1;
    q[0].push({sx,sy});q[1].push({ex,ey});
    while(!q[0].empty()||!q[1].empty()){
        res++;
        if(bfs(0)) return res;
        if(bfs(1)) return res;
        if(bfs(1)) return res;
    }
    return -1;
}

int main(){
    scanf("%d %d", &n, &m);
    getchar();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>mp[i][j];
            if(mp[i][j]=='C'){
                sx=i,sy=j;
            }
            else if(mp[i][j]=='D'){
                ex=i,ey=j;
            }
        }
    }
    int tmp=sol();
    if(tmp==-1) puts("NO");
    else{
        puts("YES");
        cout<<tmp<<endl;
    }
    return 0;
}