双向bfs

参考博客

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int const N=1e3+7;
int n,m,sx1,sy1,sx2,sy2,f;
char ch[N][N];
struct L{
    int x,y,t;
};
queue<L>q[2];
int vis[N][N][3];
int xx[]={1,-1,0,0,1,-1,1,-1};
int yy[]={0,0,1,-1,1,-1,-1,1};
int bfs(int x){
    int zt=q[x].size();
    while(zt--){
        for(int i=0;i<8-x*4;++i){
            int dx=q[x].front().x+xx[i];
            int dy=q[x].front().y+yy[i];
            int dt=q[x].front().t+f;
            if(dx>=1&&dx<=n&&dy>=1&&dy<=m&&!vis[dx][dy][x]&&ch[dx][dy]=='.'){
                if(vis[dx][dy][1-x]) retur***is[dx][dy][x]=1;
                q[x].push((L){dx,dy,dt});
            }
        }
        q[x].pop();
    }
    return 0;
}
int solve(){
    int z=0;
    while(!q[0].empty()||!q[1].empty()){
        f=1;
        if(z=bfs(0)) return z;
        if(z=bfs(1)) return z;
        f=0;
        if(z=bfs(1)) return z;
    }
    return 0;
}
int main(){
    cin >> n >> m;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            cin >> ch[i][j];
            if(ch[i][j]=='C') sx1=i,sy1=j;
            if(ch[i][j]=='D') sx2=i,sy2=j;
        }
    }
    vis[sx1][sy1][0]=1;vis[sx2][sy2][1]=1;
    q[0].push( (L){sx1,sy1,0} );
    q[1].push( (L){sx2,sy2,0} );
    int ans=solve();
    if(ans){
        cout << "YES\n";
        cout << ans;
    }
    else cout << "NO";
    return 0;
}