小A与小B

题意

一个的迷宫，小A每次可以移动一个位置，而小B每次可以移动两次位置，小A移动的方向是上下左右左上左下右上右下8个方向，小B移动的方向是上下左右4个方向，请问他们最早什么时候能够找到对方？

分析

先对小A进行bfs，求出每个格子的访问时间，再对小B进行bfs，求出每格相遇的时间，统计结果。

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
const int inf = 0x3f3f3f3f;
const int maxn = 1110;
const int M = 1e9+7;
int n,m,ans = 1e6;

char s[maxn][maxn];

int tim[2][maxn][maxn];        //0表示小A，1表示小B

int to[8][2] = {0,1,1,0,0,-1,-1,0,1,1,-1,1,-1,-1,1,-1};

void bfs(int k,int x,int y)
{
    tim[k][x][y] = 0;
    queue<pii> q;
    q.push({x,y});
    while(!q.empty())
    {
        x = q.front().first;y = q.front().second;q.pop();
        for(int i = 0; i < 8; i++)
        {
            int xx = x + to[i][0];
            int yy = y + to[i][1];
            if(xx > n || yy > m || x <= 0 || y <= 0 || tim[k][xx][yy] < inf) continue;
            if(s[xx][yy] == '#') continue;
            tim[k][xx][yy] = tim[k][x][y]+1;
            q.push({xx,yy});
        }
    }
}

void bfs2(int x,int y)
{
    tim[0][x][y] = 0;
    queue<pii> q;
    q.push({x,y});
    while(!q.empty())
    {
        x = q.front().first;y = q.front().second;q.pop();
        ans = min(ans,max(tim[1][x][y],(tim[0][x][y]+1)/2));
        for(int i = 0; i < 4; i++)
        {
            int xx = x + to[i][0];
            int yy = y + to[i][1];
            if(xx > n || yy > m || x <= 0 || y <= 0 || tim[0][xx][yy] < inf) continue;
            if(s[xx][yy] == '#') continue;
            tim[0][xx][yy] = tim[0][x][y]+1;
            q.push({xx,yy});
        }
    }
}

signed main()
{
    cin>>n>>m;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            tim[0][i][j] = tim[1][i][j] = inf;
        }
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            cin>>s[i][j];
        }
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            if(s[i][j] == 'C')
            {  
                bfs(1,i,j);
            }
        }
    }
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            if(s[i][j] == 'D')
            {  
                bfs2(i,j);
            }
        }
    }
    if(ans == 1e6)
    {
        puts("NO");
    }
    else
    {  
        puts("YES");
        cout<<ans<<endl;
    }
    return 0;
}