【洛谷】 P1162 填涂颜色
题目描述
作者：黑桃️
由数字000组成的方阵中，有一任意形状闭合圈，闭合圈由数字111构成，围圈时只走上下左右444个方向。现要求把闭合圈内的所有空间都填写成222.例如：6×66 \times 66×6的方阵（n=6n=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≤n≤30)n(1 \le n \le 30)n(1≤n≤30)
接下来nnn行，由000和111组成的n×nn \times nn×n的方阵。
方阵内只有一个闭合圈，圈内至少有一个000。
//感谢黄小U饮品指出本题数据和数据格式不一样. 已修改(输入格式)
输出格式
已经填好数字222的完整方阵。
输入输出样例 输入 #16
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
1≤n≤301 \le n \le 301≤n≤30
思路首先要先找到dfs的入口，我选择的入口是被包围那部分中的任意一个。
被包围的部分的特征：一直往上，下，左，右走（直走，不拐弯）必定会遇到围墙，因此查找一下即可找到入口，进入dfs后，把不是围墙的地方都染色就行了。（思路很简单，就是代码看着有点长）
代码#include
#include
#include
#include
#include
#include
using namespace std;
int n;
int map[40][40]; //地图
bool vis[40][40]={false}; //标记是否访问过
int dx[]={1,-1,0,0}; //四个方向
int dy[]={0,0,1,-1};
void dfs(int x,int y)
{
for(int i=0;i=0 && newx=0 && newy<n && vis[newx][newy]==false && map[newx][newy]==0) //不出界 且不是围墙
{
vis[newx][newy]=1; //标记访问过
map[newx][newy]=2; //染色
dfs(newx,newy);
}
}
}
bool in(int x,int y) //判断是否在围墙内，直走四个方向都有围墙，则在围墙内
{
int up=0,down=0,right=0,left=0;
for(int i=x;i=0;i--)
{
if(map[i][y]==1) //上有围墙
{
up=1;
break;
}
}
for(int i=y;i=0;i--)
{
if(map[x][i]==1) //左有围墙
{
left=1;
break;
}
}
if(up && down && right && left) //四面都有围墙（在围墙内），可为入口
return 1;
return 0;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++)
for(int j=0;j>map[i][j];
int postx,posty,flag=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
if(map[i][j]==0) //不是围墙
{
if(in(i,j)) //在围墙内
{
postx=i; //取出位置
posty=j;
flag=1;
break;
}
}
}
if(flag==1) break;
}
vis[postx][posty]=1; //标记入口
map[postx][posty]=2; //染色入口
dfs(postx,posty);
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
cout<<map[i][j]<<" "; //输出即可
cout<<endl;
}
return 0;
}
作者：黑桃️
