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

Alex_Cui

2019-04-01 22:17:22

Solution

这一题在训练里面是放在广搜的, 实质上这题就是求解连通块的问题, 至于深搜和广搜都是可以的, 我这里使用广搜. 本题最关键的一句话是: > 方阵内**只有一个**闭合圈, 圈内**至少有一个 $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$ 即可. 代码如下: ```cpp #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]就可以得到结果了 } } ```