搜索 专题

题目链接： 洛谷 P1162 填涂颜色

题目描述

输入输出格式

时空限制

  • 时间：1000ms
  • 空间：128MB

思路

其实我还不会 BFS ，看了题解，发现有人直接用 暴力 解决了，我就好奇试了一下，结果 AC 了。真的神奇。

初始化，把所有为 0 的先改成 2，然后在 BFS 里面，先判断外围的 2 要恢复成 0，然后二重循环，把不在圈内的 2 恢复成 0，如此循环 9 次 BFS，就大功告成。

代码

#include <cstdio>
using namespace std;
int n;
int map[32][32];

void search(){
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < n; ++j){
			if(map[i][j] == 0){
				map[i][j] = 2;
			}
		}
	}
}

void bfs(){
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < n; ++j){
			if(map[i][j] == 2 && (i == 0 || j == 0)){
				map[i][j] = 0;  //边界的 0 不算在内 
			}
		}
	}
	int cnt = 9;
	while(cnt--){
		for(int i = 0; i < n; ++i){
			for(int j = 0; j < n; ++j){
				if(map[i][j] == 2 && i > 0 && j > 0){
					if(map[i-1][j] == 0 || map[i+1][j] == 0 || map[i][j-1] == 0
					 || map[i][j+1] == 0)  //不在圈内的0 
					 {
					 	map[i][j] = 0;	
					 }
				}
			}
		}
	}
}

int main(){
	scanf("%d",&n);
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < n; ++j){
			scanf("%d",&map[i][j]);
		}
	}
	search();
	bfs();
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < n; ++j){
			printf("%d",map[i][j]);
			if(j != n-1){
				printf(" ");
			}
		}
		printf("\n");
	}
	return 0;
}