洛谷P1162-填涂颜色-题解

填涂颜色

题目描述

由数字 $0$ 组成的方阵中，有一任意形状闭合圈，闭合圈由数字 $1$ 构成，围圈时只走上下左右 $4$ 个方向。现要求把闭合圈内的所有空间都填写成 $2$。例如：$6\times 6$ 的方阵（$n=6$），涂色前和涂色后的方阵如下：

0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1

0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1

输入格式

每组测试数据第一行一个整数 $n(1 \le n \le 30)$。

接下来 $n$ 行，由 $0$ 和 $1$ 组成的 $n \times n$ 的方阵。

方阵内只有一个闭合圈，圈内至少有一个 $0$。

输出格式

已经填好数字 $2$ 的完整方阵。

样例 #1

样例输入 #1

6
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1

样例输出 #1

0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1

提示

对于 $100\%$ 的数据，$1 \le n \le 30$。

P1162 填涂颜色 - 洛谷

思路

这题其实和P1451 求细胞数量 - 洛谷很像，都是搜索求连通块数量。不过这道题是需要先反转过来全部的0和2，然后通过搜索求在边界上的连通块数量。每次搜索到一个连通块，就将其染色成0，这样当边界上无连通块时，也就是搜索结束时，题目得解。

对于反转全图的0和2，我们可以在输入的同时完成反转

输入地图

//这里用了左值引用的写法
//比传统for (int i = 0; i < n; i++)更加方便和安全
for (auto &i: mat) {
    i.resize(n);
    for (auto &j: i) {
        int tmp;
        cin >> tmp;
        j = tmp ? 1 : 2;
    }
}

查找边界的连通块

//C++ 11匿名函数写法
//这里用[&]，写在主函数里可以避免声明全局变量
auto find = [&] {
    for (int i = 0; i < n; ++i)
        if (mat[i][0] == 2) {
            x = i, y = 0;
            return true;
        } else if (mat[i][n - 1] == 2) {
            x = i, y = n - 1;
            return true;
        }
    for (int i = 0; i < n; ++i)
        if (mat[0][i] == 2) {
            x = 0, y = i;
            return true;
        } else if (mat[n - 1][i] == 2) {
            x = n - 1, y = i;
            return true;
        }
    return false;
};

//C 标准函数写法
//用到的变量都需要记得声明为全局变量
bool find() {
    for (int i = 0; i < n; ++i)
        if (mat[i][0] == 2) {
            x = i, y = 0;
            return true;
        } else if (mat[i][n - 1] == 2) {
            x = i, y = n - 1;
            return true;
        }
    for (int i = 0; i < n; ++i)
        if (mat[0][i] == 2) {
            x = 0, y = i;
            return true;
        } else if (mat[n - 1][i] == 2) {
            x = n - 1, y = i;
            return true;
        }
    return false;
};

每次搜索的核心代码

for (auto &i : visited)
    fill_n(i, n, false);
queue<pos> q;
q.push({x, y});
mat[x][y] = 0;
visited[x][y] = true;
while(not q.empty()) {
    int X = q.front().x, Y = q.front().y;
    q.pop();
    for(int i = 0; i < 4; ++i) {
        int px = X + dx[i], py = Y + dy[i];
        if(px >= 0 and px < n and py >= 0 and py < n
           and not visited[px][py] and mat[px][py] == 2) {
            mat[px][py] = 0;
            q.push({px, py});
        }
    }
}

完整C++代码

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    int n;
    cin >> n;
    vector<vector<int> > mat(n);
    bool visited[n][n];
    for (auto &i: mat) {
        i.resize(n);
        for (auto &j: i) {
            int tmp;
            cin >> tmp;
            j = tmp ? 1 : 2;
        }
    }
    int x, y;
    auto find = [&] {
        for (int i = 0; i < n; ++i)
            if (mat[i][0] == 2) {
                x = i, y = 0;
                return true;
            } else if (mat[i][n - 1] == 2) {
                x = i, y = n - 1;
                return true;
            }
        for (int i = 0; i < n; ++i)
            if (mat[0][i] == 2) {
                x = 0, y = i;
                return true;
            } else if (mat[n - 1][i] == 2) {
                x = n - 1, y = i;
                return true;
            }
        return false;
    };
    int dx[]{1, -1, 0, 0},
        dy[]{0, 0, 1, -1};
    struct pos { int x, y; };
    while (find()) {
        for (auto &i : visited)
            fill_n(i, n, false);
        queue<pos> q;
        q.push({x, y});
        mat[x][y] = 0;
        visited[x][y] = true;
        while(not q.empty()) {
            int X = q.front().x, Y = q.front().y;
            q.pop();
            for(int i = 0; i < 4; ++i) {
                int px = X + dx[i], py = Y + dy[i];
                if(px >= 0 and px < n and py >= 0 and py < n
                   and not visited[px][py] and mat[px][py] == 2) {
                    mat[px][py] = 0;
                    q.push({px, py});
                }
            }
        }
    }
    for (auto &i: mat) {
        for (auto &j: i)
            cout << j << ' ';
        cout.put('\n');
    }
    return 0;
}

AC截图