洛谷 [P1162 填涂颜色] {搜索|DFS}
题目描述
由数字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≤n≤30)
接下来n行，由0和1组成的n×n的方阵。
方阵内只有一个闭合圈，圈内至少有一个0。
//感谢黄小U饮品指出本题数据和数据格式不一样. 已修改(输入格式)
输出格式
已经填好数字2的完整方阵。
输入输出样例
输入 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
说明/提示
1≤n≤30
解题思路
因为题目中说明了只有一个环，所以我们只需要找到第一个值为1的点即可，此时该点的横纵坐标各加1肯定是环中的点。
完整代码
#include<bits/stdc++.h>
using namespace std
;
int a
[30][30];
int M
;
int x
[5]={0,0,1,0,-1};
int y
[5]={0,1,0,-1,0};
void dfs(int p
,int q
)
{
a
[p
][q
]=2;
for(int i
=0;i
<=4;i
++)
{
int xa
=p
+x
[i
];
int ya
=q
+y
[i
];
if(xa
>=0&&xa
<M
&&ya
>=0&&ya
<M
&&a
[xa
][ya
]==0)
{
dfs(xa
,ya
);
}
}
}
void print()
{
for(int i
=0;i
<M
;i
++)
{
for(int j
=0;j
<M
;j
++)
{
if(a
[i
][j
]==2)
{
printf("%d ",2);
}
else if(a
[i
][j
]==0)
{
printf("%d ",0);
}
else printf("%d ",1);
}
printf("\n");
}
}
int main()
{
scanf("%d",&M
);
for(int i
=0;i
<M
;i
++)
{
for(int j
=0;j
<M
;j
++)
{
scanf("%d",&a
[i
][j
]);
}
}
for(int i
=0;i
<M
;i
++)
{
for(int j
=0;j
<M
;j
++)
{
if(a
[i
][j
]==1)
{
dfs(i
+1,j
+1);
print();
return 0;
}
}
}
}
