48分求助!!!3,4,6WA了!!!

P1162 填涂颜色

taoyize @ 2023-11-18 20:38:05

源代码如下

#include<bits/stdc++.h>
using namespace std;
const int mx=31;
struct node{
    int x,y;
};
queue<node> q;
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
int n,a[mx][mx],b[mx][mx],ans[mx][mx];bool vis[mx][mx];
bool check(int x,int y){
    if(x>=0&&y>=0&&x<n&&y<n&&vis[x][y]&&a[x][y]==0) return true;
    else return false;
}
bool bfs(node m){
    bool ans1=false;
    q.push(m);
    while(!q.empty()){
        node nw=q.front();
        if(nw.x==0||nw.y==0||nw.x==n-1||nw.y==n-1) ans1=true;
        q.pop();
        for(int i=0;i<4;i++){
            int nx=nw.x+dx[i];
            int ny=nw.y+dx[i];
            if(check(nx,ny)){
                vis[nx][ny]=false;
                b[nx][ny]=3;
                q.push({nx,ny});
            }
        }
    }
    return ans1;
}
void draw(bool x){
    if(x){
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(b[i][j]==3) ans[i][j]=0;
            }
        }
    }
    else{
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(b[i][j]==3) ans[i][j]=2;
            }
        }
    }
}
void clear(){
    memset(b,0,sizeof(b));
}
int main(){
    memset(vis,true,sizeof(vis));
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++) cin>>a[i][j];
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(a[i][j]==0){
                draw(bfs({i,j}));
                clear();
            }
            else ans[i][j]=1;
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cout<<ans[i][j]<<" ";
        }
        cout<<endl;
    }
}

大佬求助 !!!! 小萌新学习BFS的坎坷之路。。。


by taoyize @ 2023-11-18 20:59:42

OKOK 经过长时间的努力,大约1h的思考,终于找到bug了!!!!

每一次广度搜索的时候vis没清空。。。。

为什么每次都是这种小问题啊啊啊!!!!!


by danlao @ 2023-11-18 21:13:19

呃……(我刚去找你WA代码,结果马上看到你的AC代码)


|