每日一题 6.5 小A与小B

双向广搜的模板题 唯一要注意的是小b走两步分为走两次
收获是又学习了别人精简的写法 更新了自己的板子.....
希望别人也能学习
代码有详细注释

#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 N=1005;
const int d[8][2]={{0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
int n,m;
bool v[2][N][N];///1 a    2 b
queue<pii> q[2];
char a[N][N];
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+d[k][0];
            int dy=p.se+d[k][1];
            if(dx>=1&&dx<=n&&dy>=1&&dy<=m&&a[dx][dy]!='#'&&!v[x][dx][dy])///这一步能走
            {
                if(v[x^1][dx][dy])return 1;///碰面
                v[x][dx][dy]=1;
                q[x].push(mp(dx,dy));
            }
        }
    }
    return 0;
}
int solve(){
    int ins=0;
    while(!q[0].empty()||!q[1].empty())
    {
        ins++;
        if(bfs(0))return ins;
        if(bfs(1))return ins;
        if(bfs(1))return ins;///走两次来代替走两步
    }
    return -1;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            if(a[i][j]=='C')q[0].push(mp(i,j));///输入 a b 初始坐标
            if(a[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;
}