P1162 填涂颜色

题目链接

P1162 填涂颜色

思路

本题目与P1506 拯救oibh总部的类型是相似的，都是搜索题，本题仍采用广度优先搜索，由于链接文章介绍了一些前置知识，故在本文不作解释，如果对 $queue,pair$ 的使用有疑惑，可以参考链接文章的前置知识部分。

本题也是用洪水填充的模型写的，先将地图最外围所有值为0的坐标加入待搜索队列 $seek$ 中，然后在一个 $while$ 循环中搜索，每轮循环将搜索范围从该待搜索坐标向它的上下左右扩散，如果它上下左右的坐标为0，并且没有遍历过，则将这些新坐标加入待添加队列。

可以使用一个 $bool$ 类型的二维数组 $isVisit[][]$ 记录某个坐标是否遍历过，此外，该数组还能表示该坐标是否不需要染色。如果遍历过一个坐标，则说明这个坐标上的数字是0；由于本题采用的模型为洪水填充，故如果遍历过一个坐标，那么这个坐标与最外围的0连通，即不需要染色；再对 $isVisit[][]$ 中某个元素为真的情况细分，可以得到“如果原方阵上该位置为1，则输出1；否则输出0”的结论，这将用于输出染色后的方阵。

代码

#include <iostream>
#include <queue>								// queue容器的头文件
using namespace std;
const int N = 35;								// 数组大小
int n;											// 方阵的行数或列数
// 广搜常用的方向数组，分别为向上、向下、向右、向左
int dir[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
char map[N][N];									// 存储方阵的元素
bool isVisit[N][N];								// 判断该坐标是否被遍历过
int main() {
    cin >> n;
    for (int r = 1; r <= n; ++r) {
        for (int c = 1; c <= n; ++c) {
            cin >> map[r][c];
        }
    }
	queue<pair<int, int>> seek;					// 存储待搜索坐标
	// 搜索第一列和最后一列中为0的元素
    for (int r = 1; r <= n; ++r) {
        if (map[r][1] == '0') {					// 如果该坐标的元素为0
            seek.push(make_pair(r, 1));			// 则将该坐标加入待搜索队列
            isVisit[r][1] = true;				// 并且遍历过该坐标
        }
        if (map[r][n] == '0') {					// 如果该坐标的元素为0
            seek.push(make_pair(r, n));			// 则将该坐标加入待搜索队列
            isVisit[r][n] = true;				// 并且遍历过该坐标
        }
    }
    // 搜索第一行和最后一行中为0的元素
    for (int c = 2; c < n; ++c) {
        if (map[1][c] == '0') {					// 如果该坐标的元素为0
            seek.push(make_pair(1, c));			// 则将该坐标加入待搜索队列
            isVisit[1][c] = true;				// 并且遍历过该坐标
        }
        if (map[n][c] == '0') {					// 如果该坐标的元素为0
            seek.push(make_pair(n, c));			// 则将该坐标加入待搜索队列
            isVisit[n][c] = true;				// 并且遍历过该坐标
        }
    }
    while (seek.size() > 0) {					// 直到待搜索队列没有元素为止
    	// r和c分别是待搜索队列第一个元素的行数和列数
        int r = seek.front().first, c = seek.front().second;
        seek.pop();								// 将该坐标从队列中移除
        // 遍历该坐标的上下左右方向
        for (int i = 0; i < 4; ++i) {
        	// ir和ic分别该坐标上下左右方向的坐标的行数和列数
            int ir = r + dir[i][0], ic = c + dir[i][1];
            // 如果 对应的元素值为0 并且 没有遍历过
            if (map[ir][ic] == '0' && !isVisit[ir][ic]) {
                seek.push(make_pair(ir, ic));	// 则将新坐标加入队列
                isVisit[ir][ic] = true;			// 并且遍历过新坐标
            }
        }
    }
    // 输出染色后的方阵
    for (int r = 1; r <= n; ++r) {
        for (int c = 1; c <= n; ++c) {
            if (isVisit[r][c]) {
                cout << "0 ";
            } else if (map[r][c] == '1') {
                cout << "1 ";
            } else {
                cout << "2 ";
            }
        }
        cout << '\n';
    }
    return 0;
}