题解 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]就可以得到结果了
	}
}