题目描述

由数字0组成的方阵中，有一任意形状闭合圈，闭合圈由数字1构成，围圈时只走上下左右4个方向。现要求把闭合圈内的所有空间都填写成2.例如：6 × 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(1≤n≤30)
接下来n行，由0和1组成的n × n的方阵。
方阵内只有一个闭合圈，圈内至少有一个00。

输出格式

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

输入输出样例

输入 #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
说明/提示
1 <= n <= 30

解法思路

我最初的解法是：从地图0点遍历到(n-1)*(n-1)点，如果是没搜索过的点就从这个点调用bfs(实际bfs最多只会调用两次),在bfs中把所有0点标记出来，如果遇到墙回退，遇到边界就说明是外圈，而如果最后bfs的队列空了则说明是在圈内，把内圈全部标为2后就可以输出了。
这个解法可以ac，但是我看见题解里有一个解法很不错，代码也很精简，这里重点说一下。
思路是从下标1开始接收地图，然后搜索时从0，0点搜到n+1,n+1点，也就是模拟外面加了一圈0,用dfs从外圈的0,0点开始搜索，之所以外面加一圈就是以防起始点就是墙搜索就直接结束了。搜索时把0都改为-1(做标记，这个随意),遇见墙或边界或走过的点就回退，最后地图中还剩的0点就都是圈内了。只要在打印时，把-1点打印为0,把1点正常打印为1，把0点打印为2即可。

源码

#include<iostream>
#define maxn 35

using namespace std;

int n;
int map[maxn][maxn];
int xa[4] = { 0,0,-1,1 };
int ya[4] = { -1,1,0,0 };

void dfs(int x, int y) {
    //越界或遇墙或已染色
    if (x<0 || x>n + 1 || y<0 || y>n + 1 || map[x][y] == -1||map[x][y]==1)return;
    map[x][y] = -1;     //染色
    for (int i = 0; i < 4; i++)dfs(x + xa[i], y + ya[i]);
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> map[i][j];
    dfs(0, 0);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            if (map[i][j] == -1)cout << "0 ";
            else if (map[i][j] == 0)cout << "2 ";
            else cout << "1 ";
        cout << endl;
    }

    return 0;
}