P1162 填涂颜色

Wesley13
• 阅读 660

题目描述

由数字 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)

接下来 nn 行,由 00 和 11 组成的 n \times nn×n 的方阵。

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

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

输出格式:

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

输入输出样例

输入样例#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≤n1≤n≤30≤30

题解

由边缘开始搜索,凡是可以到达的的00全部改为−1−1,最后输出时特判一下。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=50;
int mapp[MAXN][MAXN];
struct node{
    int x,y;
};
int n;
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
void bfs(int x,int y)
{
    node p;
    p.x=x;
    p.y=y;
    queue<node> q;
    q.push(p);
    while(!q.empty()) {
        node s;
        s=q.front();
        q.pop();
        for(int i=0;i<4;i++) {
            int kx=s.x+dx[i];
            int ky=s.y+dy[i];
            if(kx>=0&&kx<n&&ky>=0&&ky<n&&mapp[kx][ky]==0)
            {
                node z;
                z.x=kx;z.y=ky;
                q.push(z);
                mapp[kx][ky]=-1;
            }
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            scanf("%d",&mapp[i][j]);
    for(int i=0;i<n;i++){
        if(mapp[0][i]==0) bfs(0,i);
        if(mapp[n-1][i]==0) bfs(n-1,i);
        if(mapp[i][0]==0) bfs(i,0);
        if(mapp[i][n-1]==0) bfs(i,n-1);
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++) {
            if(mapp[i][j]==-1) printf("0 ");
            else if(mapp[i][j]==1) printf("1 ");
            else if(mapp[i][j]==0) printf("2 ");
        }
        printf("\n");
    }

    return 0;
}
点赞
收藏
评论区
推荐文章
Easter79 Easter79
3年前
typeScript数据类型
//布尔类型letisDone:booleanfalse;//数字类型所有数字都是浮点数numberletdecLiteral:number6;lethexLiteral:number0xf00d;letbinaryLiteral:number0b101
Wesley13 Wesley13
3年前
java中比较两个时间的差值
项目背景1.某篇文稿的发布时间是publishDate,例如:2020072118:00:41。2.现要求判断该篇文稿的发布时间是否在近30天之内。publicstaticlongdayDiff(DatecurrentDate,DatepublishDate){LongcurrentTimecurrentDat
Wesley13 Wesley13
3年前
java8之lambda表达式(变量作用域)
通常,我们希望能够在lambda表达式的闭合方法或类中访问其他的变量,例如:package java8test;public class T1 {    public static void main(String args) {        repeatMessage("Hello", 20);
Wesley13 Wesley13
3年前
FLV文件格式
1.        FLV文件对齐方式FLV文件以大端对齐方式存放多字节整型。如存放数字无符号16位的数字300(0x012C),那么在FLV文件中存放的顺序是:|0x01|0x2C|。如果是无符号32位数字300(0x0000012C),那么在FLV文件中的存放顺序是:|0x00|0x00|0x00|0x01|0x2C。2.  
Wesley13 Wesley13
3年前
Codevs 1159最大全0子矩阵
题目描述Description在一个0,1方阵中找出其中最大的全0子矩阵,所谓最大是指O的个数最多。输入描述InputDescription输入文件第一行为整数N,其中1<N<2000,为方阵的大小,紧接着N行每行均有N个0或1,相邻两数间严格用一个空格隔开。输出描述OutputDescription
Stella981 Stella981
3年前
Codeforces997C Sky Full of Stars 【FMT】【组合数】
题目大意:一个$n\n$的格子,每个格子由你填色,有三种允许填色的方法,问有一行或者一列相同的方案数。题目分析:标题的FMT是我吓人用的。一行或一列的问题不好解决,转成它的反面,没有一行和一列相同的方案数。从一个方向入手,比如列,把一列看成一个整体。把颜色看成二进制数,$001$,$010$,$100$。那么一列构成了一个长度为$3
Wesley13 Wesley13
3年前
445,BFS和DFS两种方式解岛屿数量
Howeverdarkandscarytheworldmightberightnow,therewillbelight.无论世界现在有多黑暗,多可怕,终有一天会重现光明。问题描述给你一个由'1'(陆地)和'0'(水)组成的的二维网格,请你计算网格中岛屿的数量。岛屿总是被水包围,并且每座岛屿只能由水平方向或
Wesley13 Wesley13
3年前
uva 253
习题44骰子涂色(Cubepainting,UVa253)输入两个骰子,判断二者是否等价。每个骰子用6个字母表示,如图47所示。图47骰子涂色例如rbgggr和rggbgr分别表示如图48所示的两个骰子。二者是等价的,因为图48(a)所示的骰子沿着竖直轴旋转90°之后就可以得到图48(b)所示的骰子。!这里写图片描述(
Wesley13 Wesley13
3年前
Java解决括号匹配算法问题
有效字符串需满足:左括号必须用相同类型的右括号闭合。包括:“()”,“\\”,“{}”。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。思路:在这里我们使用栈来实现。遍历字符串时判断:如果是左括号,那么我们将其入栈;如果为右括号,我们先判断栈是否为空(有可能字符串刚开始就是一个右括号呢),为空的话直接返回false,不为空
京东云开发者 京东云开发者
2个月前
对比 Vitess,ShardingSphere 有哪些不同
本篇为InfoQ中文站供稿原文链接:\ShardingSphere是什么?ShardingSphere是一套开源的分布式数据库中间件解决方案组成的生态圈,它由ShardingJDBC、ShardingProxy和ShardingSidecar(规划中)这3