洛谷 P1162 填涂颜色

题目：填涂颜色

网址：https://www.luogu.com.cn/problem/P1162

题目描述

由数字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。

输出格式

已经填好数字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

这道题乍一看比较难，实际想想其实也就是flood-fill。

考虑：什么是严格意义上“闭合”的？

如果对于一个联通块，它不“挨着”边缘，便可以判定它是“闭合的”。

那么我们可以将边缘上的所有位置进行广搜，碰到1便停止扩展了，被扩展的位置标记，最后没有被标记的位置即为所求！

代码如下：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define pa pair <int , int>
#define maxn 100
using namespace std;
const int dx[4] = {-1 , 1 , 0 , 0};
const int dy[4] = {0 , 0 , -1 , 1};
bool book[maxn][maxn];
int n , map[maxn][maxn];
bool valid(pa rec) {
	if(rec.first < 0 || rec.first > n - 1 || rec.second < 0 || rec.second > n - 1) return false;
	if(book[rec.first][rec.second] || map[rec.first][rec.second]) return false;
	return true;
}
void bfs()
{
	queue <pa> Q;
	while(!Q.empty()) Q.pop();
	if(map[0][0] == false) Q.push(make_pair(0 , 0));
	if(map[0][n - 1] == false) Q.push(make_pair(0 , n - 1));
	if(map[n - 1][0] == false) Q.push(make_pair(n - 1 , 0));
	if(map[n - 1][n - 1] == false) Q.push(make_pair(n - 1 , n - 1));
	for(int i = 1; i < n - 1; ++ i)
	{
		if(map[0][i] == false) Q.push(make_pair(0 , i));
		if(map[i][0] == false) Q.push(make_pair(i , 0));
		if(map[n - 1][i] == false) Q.push(make_pair(n - 1 , i));
		if(map[i][n - 1] == false) Q.push(make_pair(i , n - 1));
	}
	while(!Q.empty())
	{
		pa now = Q.front() , next;
		Q.pop();
		for(int i = 0; i < 4; ++ i)
		{
			next = make_pair(now.first + dx[i] , now.second + dy[i]);
			if(!valid(next)) continue;
			book[next.first][next.second] = true;
			Q.push(next);
		}
	}
	return;
}
int main()
{
	scanf("%d" , &n);
	for(int i = 0; i < n; ++ i)
		for(int j = 0; j < n; ++ j)
			scanf("%1d" , &map[i][j]);
	
	memset(book , 0 , sizeof(book));
	bfs();
	for(int i = 0; i < n; ++ i)
	{
		for(int j = 0; j < n; ++ j)
		{
			if(map[i][j] == 1) printf("1 ");
			else if(book[i][j]) printf("0 ");
			else printf("2 ");
		}
		puts("");
	}
	puts("");
	return 0;
}