题解 P1162 【填涂颜色】使用BFS求连通块

· · 题解

这一题在训练里面是放在广搜的, 实质上这题就是求解连通块的问题, 至于深搜和广搜都是可以的, 我这里使用广搜.

本题最关键的一句话是:

方阵内只有一个闭合圈, 圈内至少有一个 0.

这句话帮我们排除了一个很复杂的情况, 就是圈套圈的情况, 这样问题就变的简单一些了. (如果没有这句话的话就需要处理圈套圈的情况了, 审题很重要)

其次我们想到, 既然只有一个圈, 就意味着圈内全涂色, 圈外不涂色, 那么我们就会想到通过标记与边相邻的连通块, 没有标记过的 0 自然就是要涂色的, 好了思路到这里, 说明已经成功一半了.

那么这种方法有一个缺点, 就是必须遍历一边边缘才能确定所有与边缘相邻的连通块, 否则就无法处理下面这种情况, 那有没有更加方便的方法呢?

\begin{matrix} 0&0&0&\color{red}1&\color{red}1&\color{red}1&0&0 \\ 0&0&1&\color{red}1&0&\color{red}1&\color{red}1&\color{red}1 \\ 0&\color{red}1&\color{red}1&0&0&0&0&\color{red}1 \\ \color{red}1&\color{red}1&0&0&0&0&\color{red}1&\color{red}1 \\ \color{red}1&0&0&0&0&0&\color{red}1&0 \\ \color{red}1&\color{red}1&0&0&0&\color{red}1&\color{red}1&0 \\ 0&\color{red}1&\color{red}1&\color{red}1&0&\color{red}1&0&0 \\ 0&0&0&\color{red}1&\color{red}1&\color{red}1&0&0 \end{matrix}

在题目中我们可以知道 1 组成的是一个闭合圈, 所以我们只要将四周各扩宽 1 格就得到了一个全是 0 的圈, 这样就吧所有与边相邻的连通块都链接成了一个完整的连通块, 那么此时整张图就变成了两个连通块, 分别为圈内和圈外两个, 那么我们只需要从 (0, 0) 开始搜索连通块并标记, 最后输出没有标记的 0 即可.

代码如下:

#include <iostream>
#include <queue>

using namespace std;

void bfs(short *m, short n);

int main() {
    short n;
    cin >> n;
    n += 2; // 图要向四周各扩宽一个单位
    short *matrix = new short[n * n];
    memset(matrix, 0, sizeof(short) * n);
    for (int i = 1; i < n - 1; ++i) {
        matrix[i * n] = matrix[i * n - 1] = 0;
        for (int j = 1; j < n - 1; ++j) cin >> matrix[i * n + j];
    }
    memset(matrix + n * (n - 1), 0, sizeof(short) * n);
    bfs(matrix, n);
    for (int i = 1; i < n - 1; ++i) {
        for (int j = 1; j < n - 1; ++j) cout << 2 - matrix[i * n + j] << ' ';
        cout << endl;
    }
    delete[] matrix;
    return 0;
}

void bfs(short *m, short n) {
    static queue<short> q;
    m[0] = 2;
    q.push(0);
    q.push(0);
    while (!q.empty()) {
        short x = q.front();
        q.pop();
        short y = q.front();
        q.pop();
        if (y + 1 < n && !m[x * n + y + 1]) m[x * n + y + 1] = 2, q.push(x), q.push(y + 1);
        if (y - 1 >= 0 && !m[x * n + y - 1]) m[x * n + y - 1] = 2, q.push(x), q.push(y - 1);
        if (x + 1 < n && !m[(x + 1) * n + y]) m[(x + 1) * n + y] = 2, q.push(x + 1), q.push(y);
        if (x - 1 >= 0 && !m[(x - 1) * n + y]) m[(x - 1) * n + y] = 2, q.push(x - 1), q.push(y);
        // 这里我把访问过的部分标记为2, 那么在输出的时候用2 - m[x * n + y]就可以得到结果了
    }
}