填涂颜色
题目描述
由数字
0
0
0 组成的方阵中，有一任意形状的由数字
1
1
1 构成的闭合圈。现要求把闭合圈内的所有空间都填写成
2
2
2。例如：
6
6
6times 6
66 的方阵（
n
=
6
n=6
n=6），涂色前和涂色后的方阵如下：
如果从某个
0
0
0 出发，只向上下左右
4
4
4 个方向移动且仅经过其他
0
0
0 的情况下，无法到达方阵的边界，就认为这个
0
0
0 在闭合圈内。闭合圈不一定是环形的，可以是任意形状，但保证闭合圈内的
0
0
0 是连通的（两两之间可以相互到达）。
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
输入格式
每组测试数据第一行一个整数
n
(
1
≤
n
≤
30
)
n(1 le n le 30)
n(1≤n≤30)。
接下来
n
n
n 行，由
0
0
0 和
1
1
1 组成的
n
n
n times n
nn 的方阵。
方阵内只有一个闭合圈，圈内至少有一个
0
0
0。
输出格式
已经填好数字
2
2
2 的完整方阵。
样例 #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
提示
对于服务器托管网
100
%
100%
100% 的数据，
1
≤
n
≤
30
1 le n le 30
1≤n≤30。
题目分析1
如果我们按照常规思路去寻找闭合圈内任意一点，则需要将闭合圈外的点全部标记一遍，使之与闭合圈内的点分开。然后找到闭合圈内一点去进行洪水填充。需要进行两次深搜。
代码如下：
#include
using namespace std;
int a[35][35];
int n;
bool vis[35][35];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
void dfs1(int x,int y){
vis[x][y]=1;//标记
for(int i=0;in+1||ny>n+1)continue;//外侧加了一圈0，使之连通
if(vis[nx][ny]==1)continue;//已经在当前路径中
if(a[nx][ny]==1)continue;
dfs1(nx,ny);
}
}
void dfs2(int x,int y){
a[x][y]=2;//标记
for(int i=0;in||ny>n)continue;//出地图
if(a[nx][ny]!=0)continue;
dfs2(nx,ny);
}
}
void print(){
for(int i=1;i>n;
for(int i=1;i>a[i][j];
}
}
dfs1(0,0);
for(int i=1;i题目分析2
假设我们一开始将所有的0记为2，那么只需要对闭合圈外的2进行洪水填充即可，只需要使用一次深搜。
代码如下：
#include
using namespace std;
int a[35][35];
int n;
bool vis[35][35];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
void dfs(int x,int y){
vis[x][y]=1;//标记
a[x][y]=0;
for(int i=0;in+1||ny>n+1)continue;//出地图
if(a[nx][ny]==1)continue;
if(vis[nx][ny])continue;//已经在当前路径中
服务器托管网 dfs(nx,ny);
}
}
int main(){
cin>>n;
for(int i=1;i>a[i][j];
if(a[i][j]==0)a[i][j]=2;
}
}
dfs(0,0);
for(int i=1;i服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
相关推荐: 持续集成交付CICD：Linux 部署 Jira 9.12.1
目录 一、实验 1.环境 2.K8S master节点部署Jira 3.Jira 初始化设置 4.Jira 使用 一、实验 1.环境 （1）主机 表1 主机 主机 架构 版本 IP 备注 master1 K8S master节点 1.20.6 192.168.…
