（搜索）P1162 填涂颜色

1、题目描述

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

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

2、输入格式

每组测试数据第一行一个整数n
接下来 n 行，由0和1组成的 方阵。
方阵内只有一个闭合圈，圈内至少有一个0

3、输出格式

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

4、输入输出样例

输入

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

5、说明/提示

6、思路

其实感觉这个题目难点就在于区分 边界0 和 被包围的0 ，观察方阵可以知道，我们只需要找到出现的第一个1，那么由于是闭合圈，那么其右下角的那个元素一定会是0。之后我们就只需要从这个点开始向四个方向搜索就可以了，把合法的每一个点的值都变成数字2就可以了。

1、深度搜索

#include <bits/stdc++.h>
#define N 30
using namespace std;
int n = 0;
int start_x,start_y;
int a[N+1][N+1];
bool book[N+1][N+1];
int _next[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
void dfs(int x,int y){
    int next_x,next_y;
    a[x][y] = 2;
    for(int i = 0;i < 4;i++){
        next_x = x + _next[i][0];
        next_y = y + _next[i][1];
        if(next_x < 0 || next_y < 0 || next_x >= n || next_y >= n){
            continue;
        }
        if(a[next_x][next_y] == 0){
            dfs(next_x,next_y);
        }
    }
    return;
}
int main(){
    cin >> n;
    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
            cin >> a[i][j];
        }
    }
    for(int i = 0;i < n;i++){
        bool flag = false;
        for(int j = 0;j < n;j++){
            if(a[i][j] == 1){
                start_x = i + 1;
                start_y = j + 1; // 找到第一个1，从其右下角的0开始搜索
                flag = true;
                break;
            }
        }
        if(flag) break;
    }
    dfs(start_x,start_y);
    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}