这应该是是第一次记录洛谷题库里的题目吧;
题目描述
由数字00组成的方阵中,有一任意形状闭合圈,闭合圈由数字11构成,围圈时只走上下左右44个方向。现要求把闭合圈内的所有空间都填写成22.例如:6 \times 66×6的方阵(n=6n=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≤n≤30
关于思路,放在题解下面了
题解
#include<bits/stdc++.h>
using namespace std;
int a[35][35];
int b[35][35];
int c;
int dx[5]={0,0,0,1,-1},dy[5]={0,1,-1,0,0};
int n,z,m;
void dfs(int hh,int ha)
{
if(hh<0||hh>n+1||ha<0||ha>n+1||a[hh][ha]) return;
a[hh][ha]=1;
for(int i=0;i<4;i++)
dfs(hh+dx[i],ha+dy[i]);
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>> b[i][j];
if(b[i][j]==0) a[i][j]=0;
else a[i][j]=2;
}
}
dfs(0,0); for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(a[i][j]==0) cout<<2<<" ";
else cout<<b[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
思路:
这道题还是要用DFS做
关于DFS的函数怎么写我就不多说了
关于主函数的内容,是这样的:
首先明确二维数组a和b分别代表什么:a代表的是方阵不同的地带的表示(墙体是2,墙外是1,墙内是0,这个待会就会提及了),b代表这个矩形方阵,而为了方便,我们把图中输入的“1”视为墙(不是说墙的表示是1,他是2),而我们的主要目的就是把在墙内和墙外的区别对待
输入二维数组b的时候,我们把墙表示为2,即a[i][j]=2,其余的空地我们把它看做0,即if(b[i][j]==0) a[i][j]=0,
接着就是dfs了,我们一个一个点的去遍历,当遇到墙的时候,就没法走,就只能从其他三个方向绕过这隔墙,所以墙内的画是永远然不到颜色的,即 if(撞到边界||已经遍历过) return ; 接着, a[i][j]=1;
那么我们就分离出了:墙内的是0;墙体是2;墙外的是1;
最后一步我们进行判断,if(a[i][j]==0) 给他染上色,即cout<<2,else (即墙体和墙外的)cout<<b[i][j](他们原来是啥现在就是啥)
然后就OK啦!
2022.3.6