简单的搜索题目（洛谷P1162 填涂颜色）

好久没写过算法题了，得康复一下了😭
先在洛谷练一道普及的简单题试试，练习一下简单的dfs搜索
感觉这题还不错，在此简单记录一下

题目

填涂颜色（洛谷P1162）

题目描述

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

如果从某个 $0$ 出发，只向上下左右 $4$ 个方向移动且仅经过其他 $0$ 的情况下，无法到达方阵的边界，就认为这个 $0$ 在闭合圈内。闭合圈不一定是环形的，可以是任意形状，但保证闭合圈内的 $0$ 是连通的（两两之间可以相互到达）。
0 0 0 0 0 0
0 0 0 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 1 0 1
1 1 1 1 1 1
0 0 0 0 0 0
0 0 0 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 1 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$ 。

分析

可以想象1围城的区域是一堵墙，然后周围的水冲进来，没有覆盖到的区域
不就是闭合的“1”里面的“0”，然后再改写成“2”，然后输出
我们可以通过dfs搜索，遇到墙就停下来，这里的墙有边界还有“1”，也就是
if (x < 0 || x > n+1 || y < 0 || y > n+1 || a[x][y] != 0) return;
如果不是就染上颜色

注：
我这里是读取时把墙定义为了2，染色为1

如果不是墙就搜索过去，我们可以定义dx[4],dy[4],通过for循环递归搜索也就是dfs

int dx[5] = { 0,-1,1,0,0 };
int dy[5] = { 0,0,0,1,-1 };//上下左右
for (int i = 1; i <= 4; i++) {
        dfs(x + dx[i], y + dy[i]);
    }

最后循环输出，原本墙的地方输出1，染色的地方输出0，未染色的地方输出2

for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (a[i][j] == 1)
                printf("0 ");
            else if (a[i][j] == 2)
                printf("1 ");
            else
            {
                printf("2 ");
            }
        }
        printf("\n");
    }

我的代码

#include <bits/stdc++.h>
using namespace std;

int n;
int a[32][32];
int b[32][32];//存图
int dx[5] = { 0,-1,1,0,0 };
int dy[5] = { 0,0,0,1,-1 };//上下左右


void dfs(int x, int y) {
    if (x < 0 || x > n+1 || y < 0 || y > n+1 || a[x][y] != 0)
        return;
    else
    {
        a[x][y] = 1;
    }
    for (int i = 1; i <= 4; i++) {
        dfs(x + dx[i], y + dy[i]);
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &b[i][j]);
            if (b[i][j] == 0) a[i][j] = 0;
            else
            {
                a[i][j] = 2;
            }
        }
    }
    dfs(0, 0);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (a[i][j] == 1)
                printf("0 ");
            else if (a[i][j] == 2)
                printf("1 ");
            else
            {
                printf("2 ");
            }
        }
        printf("\n");
    }
    return 0;
}