正文
洛谷P1162 填涂颜色【bfs】
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
题目链接 ：https://www.luogu.org/problemnew/show/P1162
题意：
有一个0和1组成的矩阵，一些1组成一个闭合圈，圈住一些0，现在要把被圈住的这些0变成2输出。
思路：
bfs，判断每个0可以到达的边界。
如果这个0是可以到达矩阵的边界的说明没有被圈住。
bfs时不把1加入队列，如果最后也不能到达边界说明是被圈住的，变成2就行了。
#include<stdio.h>
#include<stdlib.h>
#include<map>
#include<set>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue> using namespace std; int n;
int mat[][];
typedef pair<int, int> pr;
int dx[] = {-, , , };
int dy[] = {, , -, };
bool vis[][]; bool check(int i, int j)
{
return (i >= && j >= && i < n && j < n);
} bool bfs(int i, int j)
{
memset(vis, , sizeof(vis));
queue<pr>que;
que.push(make_pair(i, j));
while(!que.empty()){
pr p = que.front();que.pop();
if(p.first == || p.first == n - || p.second == || p.second == n - )return false;
for(int k = ; k < ; k++){
int x = p.first + dx[k], y = p.second + dy[k];
if(check(x, y) && mat[x][y] != && !vis[x][y]){
que.push(make_pair(x, y));
vis[x][y] = true;
} }
}
return true;
} int main()
{
scanf("%d", &n);
for(int i = ; i < n; i++){
for(int j = ; j < n; j++){
scanf("%d", &mat[i][j]);
}
} for(int i = ; i < n; i++){
for(int j = ; j < n; j++){
if(mat[i][j] == ){
if(bfs(i, j)){
mat[i][j] = ;
}
}
}
} for(int i = ; i < n; i++){
printf("%d", mat[i][]);
for(int j = ; j < n; j++){
printf(" %d", mat[i][j]);
}
printf("\n");
}
return ;
}
