洛谷涂填颜色问题，我用广度遍历圈外的0，时间错误要咋改啊？

Question

#include<iostream>
#include<queue> //广度搜索BFS总是和队列一起使用 
using namespace std;
int n;
int eg[35][35];
int fx[4]={-1,1,0,0};//上下
int fy[4]={0,0,-1,1};//左右四个方向 

struct node
{
	int x;
	int y;
};

bool flag=0;	
void bfs(int xx,int yy)
{
	queue<node>q;
	node p,w,v;

	p.x=xx;
	p.y=yy;
	q.push(p);	
	while(!q.empty()){
		w=q.front();
		q.pop();
		
		for(int i=0;i<4;i++){
			v.x=w.x+fx[i];
			v.y=w.y+fy[i];
			
			if(eg[w.x][w.y]==1) continue;//遇到1就停止，换另一个方向 
			if(w.x<0 || w.x>=n || w.y<0 || w.y>=n){ //范围之外，说明不在闭合圈内 
				eg[xx][yy]=-1; //对圈外的0进行染色 
				flag=1;
				break;		
			}
			q.push(v);
		}
		
		if(flag){
			flag=0;///////////////错误！！！！！！！！！！！
			break;
		} 
		
	}	
}

int main()
{
	cin>>n;		
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			cin>>eg[i][j];
	
	for(int i=0;i<n;i++)//遍历一遍所有点 
		for(int j=0;j<n;j++){
			if(eg[i][j]==0)//只遍历等于0的点 
				bfs(i,j);
				
		}		
			
	
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){//安排它 
			if(eg[i][j]==-1) cout<<0<<" ";
			if(eg[i][j]==1)  cout<<1<<" ";
			if(eg[i][j]==0)	 cout<<2<<" ";
		} 
		cout<<endl; 
	} 
	
	return 0;
}

Answer 1

您的思路有一些瑕疵。考虑到您对于每一个“0”都进行一遍 bfs，是不对的，因为闭合圈外的点不应该被染色。

请参考一下我的代码，代码里有详细的说明这题的解法：

#include<bits/stdc++.h>
using namespace std;
int n,a[40][40],xt,yt;
// 偏移量
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
void search(int x,int y)
{
    pair<int,int> p;
    deque<pair<int,int>> q;
    q.push_back(make_pair(x,y));
    a[x][y]=3;
    while(!q.empty())
    { 
        p=q.front();
        for(int i=0;i<4;i++)
        {
            xt=p.first+dx[i];
            yt=p.second+dy[i];
            if(a[xt][yt]==0)
            {
                q.push_back(pair<int,int>(xt,yt));
                a[xt][yt]=3;
            }
        }
        q.pop_front();
    }
}
/*
洪水填充算法：

对于地图

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
0 0 0 0 0 0 0 0
0 0 0 1 1 1 1 0
0 0 1 1 0 0 1 0
0 1 1 0 0 0 1 0
0 1 0 0 0 0 1 0
0 1 1 1 1 1 1 0
0 0 0 0 0 0 0 0

然后再在其周围加上一圈围墙，防止越界，这样就不用在搜索时再特意判断是否越界了
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1  0  0  0  0  0  0  0  0 -1
-1  0  0  0  0  0  0  0  0 -1
-1  0  0  0  1  1  1  1  0 -1
-1  0  0  1  1  0  0  1  0 -1
-1  0  1  1  0  0  0  1  0 -1
-1  0  1  0  0  0  0  1  0 -1
-1  0  1  1  1  1  1  1  0 -1
-1  0  0  0  0  0  0  0  0 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1

现在开始从 (1,1) 的地方开始 bfs，将闭合圈外的所有空间都染成"3"。

-1 -1 -1 -1 -1 -1 -1 -1 -1 -1
-1  3  3  3  3  3  3  3  3 -1
-1  3  3  3  3  3  3  3  3 -1
-1  3  3  3  1  1  1  1  3 -1
-1  3  3  1  1  0  0  1  3 -1
-1  3  1  1  0  0  0  1  3 -1
-1  3  1  0  0  0  0  1  3 -1
-1  3  1  1  1  1  1  1  3 -1
-1  3  3  3  3  3  3  3  3 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1

这样剩下的“0”就是题中需要的闭合圈内的被染成“2”的空间，所有“3”就是题中需要的不被染色（“0”）的空间。
输出前转化一下答案即可。
*/
int main()
{
    // 初始化“围墙”
    for(int i=0;i<40;i++) for(int j=0;j<40;j++) a[i][j]=-1;
    // 加上待填充的空间
    for(int i=1;i<39;i++) for(int j=1;j<39;j++) a[i][j]=0;
    cin>>n,n+=2;
    for(int i=2;i<n;i++) for(int j=2;j<n;j++) cin>>a[i][j];
    search(1,1);
    for(int i=2;i<n;i++) for(int j=2;j<n;j++) if(a[i][j]==0) a[i][j]=2;
    for(int i=2;i<n;i++) for(int j=2;j<n;j++) if(a[i][j]==3) a[i][j]=0;
    for(int i=2;i<n;i++)
    {
        for(int j=2;j<n;j++) cout<<a[i][j]<<" ";
        cout<<endl;
    }
    return 0;
}
```c++

这是一种逆向思维，因为要将闭合圈内染色，我们不如将闭合圈外染色，反过来没有被染色的空间就在闭合圈内。因为闭合圈外的空间可能不是一个联通的整体，所以要加一圈“待填充的空间”。希望回答能对你有帮助。