题解：P1162 填涂颜色

LittleI_qwq · 2025-12-27 11:22:52 · 题解

P1162

算法

DFS（深度优先搜索）。

什么是 DFS

深度优先搜索（简称 DFS），其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。

DFS 经常被用在树上搜索根节点到叶节点的路径，或在图上搜索联通块。

如何搜索联通块

先选取一个起始点，需保证其在某一个你要搜索的联通块内。

将该点标注起来，为了防止重复搜索。
以该点为中心，向四个（或八个，本题是四个）方向探索：
- 如果周围的点已经超出了边界，那么停止；
- 如果周围的点已经被访问过了，那么停止；
- 否则递归，坐标参数传新点的坐标，回到第一步。

思路

在本题中，我们的目标是搜出一个由 1 为边框的联通块。因为这个联通块的形状可能十分不规则，比如这样：

显然无法直接搜索目标块内的 0，因为你无法直接确定哪一个数在目标块内（即无法确定深搜的起点）。

所以我们考虑将题目给定的图四周添加一圈 0。这样，块外的所有 0 都会在同一个联通块中，搜索这一个联通块，输出时特判一下即可。

该操作可以利用数组从一开始的下标实现。

代码

#include <bits/stdc++.h>
using namespace std;
int n,a[33][33],vis[33][33];
int dx[5]={0,0,1,0,-1};//横坐标变化量
int dy[5]={0,1,0,-1,0};//纵坐标变化量
void dfs(int x,int y)
{
    if(vis[x][y]||a[x][y]) return;//已经访问过了
    vis[x][y]=1;
    for(int i=1;i<=4;i++)
        if(x+dx[i]>32||x+dx[i]<0||y+dy[i]>32||y+dy[i]<0) continue;//超过了边界
        else dfs(x+dx[i],y+dy[i]);
}
int main()
{
    cin >> n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin >>a[i][j];
    //因为数组默认全填 0，所以直接从(0,0)开始搜索，就相当于添加了一圈 0
    dfs(0,0);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            if(vis[i][j]) cout << 0 << ' ';//被访问过，说明在外面的联通块内，不是我们需要的
            else if(a[i][j]) cout << 1 << ' ';//原来的墙壁
            else cout << 2 << ' ';//在我们需要的联通块内
        cout << endl;
    }
    return 0;
}