【BFS染色问题】P1162填涂颜色例题+核心逻辑

【算法思路】

要判断一个数字 0 是否在闭合圈内，可以换个角度思考。不在闭合圈内的 0 是可以从方阵的边界出发，通过上下左右移动，只经过其他 0 到达的。

• 思路①.我们可以从方阵的四条边界上的 0 开始进行广度优先搜索（BFS），将这些能从边界到达的 0 标记出来，那么剩下的未被标记的 0 就是在闭合圈内的。
• 思路②.可以先默认所有0为2，再从所有地图边缘的2进行腐蚀，未被腐蚀的就是被1保护的2

【代码示例】

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
typedef pair<int,int> PII;const int N=40;
int n;
int g[N][N];//地图矩阵 
bool st[N][N];//标记是否被访问过 
int dx[]={-1,0,1,0},dy[]={0,-1,0,1};void bfs(){queue<PII> q;//遍历队列//将四条边上的0加入队列,作为队列起点 for(int i=0;i<n;i++){if(g[0][i] == 0){q.push({0,i});//第一行st[0][i]=true;}if(g[n-1][i] == 0){q.push({n-1,i});//最后一行st[n-1][i]=true;}if(g[i][0] == 0){q.push({i,0});//第一列 st[i][0]=true;}if(g[i][n-1] == 0){q.push({i,n-1});//最后一列 st[i][n-1]=true;}} while(!q.empty()){auto t=q.front();//将队头出队 q.pop();for(int i=0;i<4;i++){int x=t.first+dx[i],y=t.second+dy[i];if(x<0 || x>=n || y<0 || y>=n) continue;//越界情况if(g[x][y]==0 && !st[x][y]){//将不在闭合圈的0入队并标记q.push({x,y});st[x][y]=true;}}}
}int main(){cin>>n;for(int i=0;i<n;i++){for(int j=0;j<n;j++){cin>>g[i][j];}}bfs();//将未被标记的0改为2for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(g[i][j]==0 && !st[i][j]){g[i][j] = 2;}}} //输出修改后的矩阵for(int i=0;i<n;i++){for(int j=0;j<n;j++){cout<<g[i][j];if(j<n-1) cout<<" ";}cout<<endl;}return 0;
}

BFS处理染色问题的核心逻辑

1. 确定起点：选择与问题条件相关的起点（如本题的边界 0）。
2. 层序遍历：使用队列逐层扩展，确保所有可达节点被访问。
3. 标记节点：通过标记数组记录节点是否被访问，避免重复处理。
4. 结果处理：根据标记数组修改目标区域（如将未标记的 0 填为 2）。