【第64题】 广度优先搜索(BFS)8连刷(四)：AtCoder AGC033 A - Darker and Darker

#include <bits/stdc++.h>

using namespace std;
#define endl '\n';

char a[1003][1003];
int n, m, ans = 0;
int len[1003][1003];
int b[1003][1003];
const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};

struct edge {
    int x, y;
};

queue<edge> v;

bool is(int x, int y) {
    return (x >= 0 && x < n && y >= 0 && y < m) && !b[x][y];
}

void bfs() {
    while (!v.empty()) {
        edge k = v.front();
        v.pop();
        for (int i = 0; i < 4; ++i) {
            if (is(k.x + dx[i], k.y + dy[i])) {
                v.push({k.x + dx[i], k.y + dy[i]});
                b[k.x + dx[i]][k.y + dy[i]] = true;
                len[k.x + dx[i]][k.y + dy[i]] = len[k.x][k.y] + 1;
                ans = max(len[k.x + dx[i]][k.y + dy[i]], ans);
            }
        }
    }
}

void best_coder() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> a[i][j];
            if (a[i][j] == '#') {
                v.push({i, j});
                b[i][j] = true;
            }
        }
    }
    bfs();
    cout << ans;
}

void happy_coder() {
}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    // 返回
    return 0;
}