每日一题 小A与小B 双向BFS

一.题意

这道题要求小A和小B最早的相遇时间。
而小A的行走规则是：每次可以走8个方向，每次走一步。
小B的行走规则是：每次可以走4个方向，但每次走两步（两步不一定是要同方向）。

二.题解

很明显分别对两个人进行bfs 计算出到达每个点两个人到达的最短时间
然后枚举两个人都能达到的点，比较取较大值，再与ans 取较小值
但是我不知道为什么一直有百分7的样例过不去
所以我参考了部分题解，用了另一种方法
类似于分层图，对两个人在两张地图同时bfs，在n*m步内有答案即输出，否则no，详细可见代码。

代码:

#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ld long double
#define ll long long
#define ull unsigned long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;

const int manx=1e6+5;
const int N=1e3+5;
const int mod=1e9+7;

char c[N][N];
bool vis[2][N][N];
queue<pair<ll,ll> >q[2];
int dx[] = { 1,0,-1,0,1,1,-1,-1 };
int dy[] = { 0,1,0,-1,-1,1,-1,1 };
ll cnt=0,n,m;

void bfs(ll f){
    ll sz=q[f].size();
    while(sz--){
        ll xx=q[f].front().fi,yy=q[f].front().se; q[f].pop();
        for(int i=0;i<4+(f?0:4);i++){
            ll x=xx+dx[i],y=yy+dy[i];
            if(x<1||x>n||y<1||y>m||c[x][y]=='#'||vis[f][x][y]) continue;
            vis[f][x][y]=1; q[f].push(mp(x,y));
            if(vis[f^1][x][y]){
                cout<<"YES\n"<<cnt<<endl;
                exit(0);
            }
        }
    }
}

int main(){
    io;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            cin>>c[i][j];
            if(c[i][j]=='C') q[0].push(mp(i,j)),vis[0][i][j]=1;
            else if(c[i][j]=='D') q[1].push(mp(i,j)),vis[1][i][j]=1;
        }
    while(cnt<=n*m){
        ++cnt;
        bfs(0);
        bfs(1); bfs(1);
    }
    cout<<"NO"<<endl;
    return 0;
}