P1162 填涂颜色 洛谷

P1162 填涂颜色

题目描述
由数字00组成的方阵中，有一任意形状闭合圈，闭合圈由数字11构成，围圈时只走上下左右44个方向。现要求把闭合圈内的所有空间都填写成22.例如：6×6的方阵（n=6），涂色前和涂色后的方阵如下：

0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 1 1 0 0 1 1 1 1
0 1 1 0 0 1 0 1 1 2 2 1
1 1 0 0 0 1 1 1 2 2 2 1
1 0 0 0 0 1 1 2 2 2 2 1
1 1 1 1 1 1 1 1 1 1 1 1

输入输出格式
输入格式：
每组测试数据第一行一个整数n(1≤n≤30)
接下来n行，由0和1组成的n×n的方阵。

方阵内只有一个闭合圈，圈内至少有一个0。

输出格式：
已经填好数字2的完整方阵。

思路：将闭合空间染色，不妨先将所有0染为2，再找出所有非在闭合圈内的点改回0，而不在闭合圈的点一定是与最外围的点连通的，因此只要把能从最外圈的点搜索进去的点全部染回0即可。

#include <bits/stdc++.h>
using namespace std;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int a[100][100];
int n;
void dfs(int x,int y){
    if(x<0||y<0||x>=n||y>=n)return;
    if(a[x][y]!=2)return;
    a[x][y]=0;
    for(int i=0;i<4;i++){
        dfs(x+dx[i],y+dy[i]);
    }
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>a[i][j];
            if(a[i][j]==0)a[i][j]=2;//先染色
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i!=0&&i!=n-1&&j!=0&&j!=n-1)continue;//遍历最外圈的点
            if(a[i][j]==2)dfs(i,j);//如果已被染色就向内搜索
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            printf("%d%c",a[i][j],j!=n-1?' ':'\n');//输出染色后的方阵
        }
    }
    return 0;
}