bfs

小A与小b

• 两次bfs即可, 怎样一次走两步呢,按一步bfs,时间变成距离/2上取整即可

#include <iostream>
#include <algorithm>
#include <cstring>

#define fs first
#define sc second
using namespace std;
typedef pair<int, int> PII;
const int N = 1010, inf = 0x3f3f3f3f;
char g[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int n, m, xd[8] = {-1, 1, 0, 0, 1, -1, 1, -1}, yd[8] = {0, 0, -1, 1, -1, -1, 1, 1};
int dist1[N][N], dist2[N][N];
bool st[N][N];
PII q[N * N];
void bfs(int sx, int sy, int dx[], int dy[], int d[N][N], int len)
{
    int hh = 0, tt = -1;
    q[++ tt] = {sx, sy};
    memset(st, 0, sizeof st);
    d[sx][sy] = 0;
    while(hh <= tt)
    {
        auto t = q[hh ++];
        if(st[t.fs][t.sc]) continue;
        st[t.fs][t.sc] = true;
        for(int i = 0; i < len; i ++)
        {
            int a = t.fs + dx[i], b = t.sc + dy[i];
            if(a < 0 || a >= n || b < 0 || b >= m || g[a][b] == '#') continue;
            if(d[a][b] > d[t.fs][t.sc] + 1)
            {
                d[a][b] = d[t.fs][t.sc] + 1;
                q[++ tt] = {a, b};
            }
        }
    }
}
int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i ++) 
        for(int j = 0; j < m; j ++)
            scanf(" %c", &g[i][j]);
    memset(dist1, 0x3f, sizeof dist1);
    memset(dist2, 0x3f, sizeof dist2);
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < m; j ++)
            if(g[i][j] == 'C')
                bfs(i, j, xd, yd, dist1, 8);
            else if(g[i][j] == 'D')
                 bfs(i, j, dx, dy, dist2, 4);
    int res = inf;
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < m; j ++)
           res = min(res, max(dist1[i][j], (dist2[i][j] + 1) / 2));
    if(res < inf) 
        cout << "YES" << endl << res << endl;
    else cout << "NO" << endl;
    return 0;
}