题解：P1162 填涂颜色

知梦 · 2025-12-28 11:52:20 · 题解

题目传送门

题目大意

把一个大小为 n \cdot n 的方阵中被 1 所包围的 0 都染色成 2 。

sol

注意到 1 \le n \le 30 显然联想到 dfs。

直接处理染色显然是不好写的。那么我们可以逆向思考一下，处理不被染色的 0，标记一下 ，在输出的时候再特判，就轻而易举的写出这道题了。

::::info[code]{open}

#include <bits/stdc++.h>
using namespace std;
int n;
int a[10010][10010];
bool vis[10010][10010];//标记数组
void dfs(int x, int y)//简单dfs
{
    if (x < 0 || y < 0 || x > n + 1 || y > n + 1 || vis[x][y] || a[x][y] == 1)//边界特判
        return;
    vis[x][y] = true;//标记不被染色的0
    dfs(x + 1, y);
    dfs(x - 1, y);
    dfs(x, y + 1);
    dfs(x, y - 1);
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> a[i][j];
    dfs(0, 0);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (!vis[i][j] && a[i][j] != 1)//特判
                cout << "2 ";
            else
                cout << a[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}
::::