题目： 填涂颜色

P1162 https://www.luogu.com.cn/problem/P1162

题目描述

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

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

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

输入格式

每组测试数据第一行一个整数 。

接下来 行，由 和 组成的 的方阵。

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

输出格式

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

输入输出样例 #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

说明/提示

对于 的数据，。

题解

代码

#include<stdio.h>
#define N 35
int dir [4][2]={{-1,0},{1,0},{0,1},{0,-1}};
struct S
{   int key;
    int state;//0为待定，1为死，2为活
} arr[N][N];

int main(){
    int n,dx,dy,count;
    scanf("%d",&n);
    for (int i=0;i<n;i++){
        for (int j=0;j<n;j++){
        scanf("%d",&arr[i][j].key);
        arr[i][j].state=0;
        
        }
    }
    printf("\n");
    for (int i=0;i<n;i++){
        for (int j=0;j<n;j++){
            if (arr[i][j].key==0){
                for (int f=0;f<4;f++){
                    count=0;
                    dx=i+dir[f][0];
                    dy=j+dir[f][1];
                    if (dx >=0 && dx<=n-1 && dy >=0 && dy<=n-1){
                        if (arr[dx][dy].key==0 && arr[dx][dy].state==2){
                            arr[i][j].state=2;
                            break;
                        }
                        else if (arr[dx][dy].key==0 && arr[dx][dy].state==1){
                            arr[i][j].state=1;
                            break;
                        }
                        else if (arr[dx][dy].key==1){
                            count++;
                        }
                    }
                    else {
                        arr[i][j].state=2;
                        break;
                    }
                    if (count==4){
                        arr[i][j].state=1;
                    }
                }
                if (arr[i][j].state==0){
                    if (arr[i+1][j].key==1 && arr[i][j+1].key==1){
                        arr[i][j].state=1;
                    
                    }
                }
            }
        }
    }
    for (int i=n-1;i>=0;i--){
        for (int j=n-1;j>=0;j--){
            if (arr[i][j].key==0 && arr[i][j].state==0){
                for (int f=0;f<4;f++){
                    dx=i+dir[f][0];
                    dy=j+dir[f][1];
                    if (arr[dx][dy].key==0 && arr[dx][dy].state==2){
                        arr[i][j].state=2;
                        break;
                    }
                    else if (arr[dx][dy].key==0 && arr[dx][dy].state==1){
                        arr[i][j].state=1;
                        break;
                    }
                }
            }
        }
    }
    for (int i=0;i<n;i++){
        for (int j=0;j<n;j++){
            if (j==n-1) printf("%d\n",arr[i][j].key);
            else{
                if (arr[i][j].state==1){
                    printf("%d ",2);
                }
                else {printf("%d ",arr[i][j].key);}
            }
        }
    }

    return 0;
}

解析

这道题先从前往后遍历一遍，找到第一个能确定的包围的0，在反过来遍历一遍，确定所有包围的0，最后输出即可。