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

题目

题目原文请移步下面的链接

• https://www.luogu.com.cn/problem/AT_agc033_a
  • 参考题解：https://www.luogu.com.cn/problem/solution/AT_agc033_a
• 标签：BFS、多点开始搜索

题解

• 小码匠思路
  • 是很典型的BFS问题，所有的黑块是同时往外扩散的，所以把所有初始黑块要一起存进队列里，后面就是常见的bfs打发了
• 官方题解
  • 题解大家可移步看这里，很多童鞋写了各种解法
    • https://www.luogu.com.cn/problem/solution/AT_agc033_a

代码

代码语言：javascript复制

#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;
}

cin int 队列 搜索 效率

0 人点赞