NC23486 小A与小B(双向BFS)

题目链接

题意：





题解：

AC代码

/*
    Author:zzugzx
    Lang:C++
    Blog:blog.csdn.net/qq_43756519
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define endl '\n'
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f;
const int dir[8][2]={{0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};

int n,m;
bool vis[2][1010][1010];
queue<pii> q[2];
char g[1010][1010];
bool bfs(int x){
    int sz=SZ(q[x]);
    while(sz--){
        pii p=q[x].front();
        q[x].pop();
        for(int k=0;k<(x?4:8);k++){
            int dx=p.fi+dir[k][0];
            int dy=p.se+dir[k][1];
            if(dx>=1&&dx<=n&&dy>=1&&dy<=m&&g[dx][dy]!='#'&&!vis[x][dx][dy]){
                if(vis[x^1][dx][dy])return 1;
                vis[x][dx][dy]=1;
                q[x].push(mp(dx,dy));
            }
        }
    }
    return 0;
}
int solve(){
    int res=0;
    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()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            cin>>g[i][j];
            if(g[i][j]=='C')q[0].push(mp(i,j));
            if(g[i][j]=='D')q[1].push(mp(i,j));
        }
    int ans=solve();
    if(ans==-1)cout<<"NO";
    else {
        cout<<"YES"<<endl;
        cout<<ans<<endl;
    }
    return 0;
}