洛谷 P1162 填涂颜色-白红宇的个人博客

洛谷 P1162 填涂颜色

发布日期：2021-08-13 19:50:34 浏览次数：11 分类：技术文章

本文共 1810 字，大约阅读时间需要 6 分钟。

题目描述

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

0 0 0 0 0 00 0 1 1 1 10 1 1 0 0 11 1 0 0 0 11 0 0 0 0 11 1 1 1 1 1

0 0 0 0 0 00 0 1 1 1 10 1 1 2 2 11 1 2 2 2 11 2 2 2 2 11 1 1 1 1 1

输入输出格式

输入格式：

每组测试数据第一行一个整数：n。其中n(1<=n<=30)

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

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

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

输出格式：

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

输入输出样例

输入样例#1：

60 0 0 0 0 00 0 1 1 1 10 1 1 0 0 11 1 0 0 0 11 0 0 0 0 11 1 1 1 1 1

输出样例#1：

0 0 0 0 0 00 0 1 1 1 10 1 1 2 2 11 1 2 2 2 11 2 2 2 2 11 1 1 1 1 1

说明

1<=n<=30

思路：搜索。

#include
         
          #include
          
           #include
           
            #include
            
             using namespace std;int n,flag=1,ff,tot=1;int dx[4]={
       0,0,1,-1};int dy[4]={
       1,-1,0,0};int map[35][35],use[35][35];void dfs(int x,int y,int tot){    use[x][y]=tot;    for(int i=0;i<4;i++){        int cx=x+dx[i];        int cy=y+dy[i];        if(cx>=1&&cx<=n&&cy>=1&&cy<=n&&!use[cx][cy]){            if(cx==1||cx==n||cy==1||cy==n)    flag=0;            dfs(cx,cy,tot);        }    }}int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++)        for(int j=1;j<=n;j++){            scanf("%d",&map[i][j]);            if(map[i][j])    use[i][j]=1;        }    for(int i=1;i<=n;i++){        ff=0;         for(int j=1;j<=n;j++)            if(!use[i][j]){                ff=1;tot++;flag=1;                dfs(i,j,tot);                if(flag)    break;            }        if(flag&&ff)    break;     }     for(int i=1;i<=n;i++)        for(int j=1;j<=n;j++)            if(use[i][j]==tot)    map[i][j]=2;    for(int i=1;i<=n;i++){        for(int j=1;j<=n;j++)            cout<
             
              <<" ";        cout<

转载于:https://www.cnblogs.com/cangT-Tlan/p/7899542.html

转载地址：https://blog.csdn.net/weixin_30699235/article/details/99132575 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：mysqldump备份不输入密码直接备份

下一篇：Java 9 揭秘（5. 实现服务）

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

题目描述

输入输出格式

输入输出样例

说明

发表评论

最新留言

关于作者

推荐文章