Luogu P1162 填涂颜色(bfs)

 P1162 填涂颜色

题目描述

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

接下来n行，由0和1组成的nXn的方阵。

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

//感谢黄小U饮品指出本题数据和数据格式不一样. 已修改(输入格式)

输出格式：

已经填好数字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

　　还是bfs解。

　　思路是先把所有的0都涂色成2　

　　然后再判断2有木有靠着边界的连通块

　　有就都涂色成0 因为靠着边界，那么这个连通块肯定没被1围住

#include <cstdio>

int map[40][40];
char book[40][40];
struct node
{
    int x, y;
}que[905];
int move[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};


int main()
{
    int n, tmp, head, tail;
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
        {
            scanf("%d", &tmp);
            if(tmp == 1)
            {
                map[i][j] = 1;
                book[i][j] = 1;        //标记不能走
            }
            else
                map[i][j] = 2;        //0涂色成2    
        }
    
    
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
        {
            //如果是2
            if(map[i][j] == 2)
            {
                int flag = 0;
                head = tail = 1;    //注意这里
                que[tail].x = i;
                que[tail].y = j;
                tail++;
                while(head<tail)
                {
                    int nx, ny;
                    for(int k=0; k<4; k++)
                    {
                        nx = que[head].x + move[k][0];
                        ny = que[head].y + move[k][1];
                        if(nx && ny && nx<=n && ny<=n && !book[nx][ny])
                        {
                            que[tail].x = nx;
                            que[tail].y = ny;
                            tail++;
                            book[nx][ny] = 1;
                        }
                        //如果出了边界 那就说明这个2靠边界 那就标记
                        else if(nx<1 || nx>n || ny<1 || ny>n)
                            flag = 1;
                    }
                    head++;
                }
                //如果标记了 那就把刚刚的连通块涂色成0
                if(flag)
                    for(int k=1; k<tail; k++)
                        map[que[k].x][que[k].y] = 0;
            }
        }
    
    //注意输入格式
    for(int i=1; i<n; i++)
    {
        for(int j=1; j<n; j++)
            printf("%d ", map[i][j]);
        printf("%d
", map[i][n]);    
    }
    for(int j=1; j<n; j++)
            printf("%d ", map[n][j]);
    printf("%d", map[n][n]);
    
    return 0;
}