除测试点3都过

P1141 01迷宫

zqh_7plus @ 2024-05-09 22:22:02

#include<bits/stdc++.h>
using namespace std;
struct q{
    int x,y;
};
queue<q> g;
int n=0,m=0,mg[1005][1005]={},fw[1005][1005]={},dx[4]={1,-1,0,0},dy[4]={0,0,1,-1},numm=0,flag[1005][1005]={},qwe=0,bh=0,flagg[100001]={};
void BFS(){
    while(!g.empty()){
        ++numm;
        int x=g.front().x,y=g.front().y;
        flag[x][y]=qwe;
        flagg[qwe]++;
            for(int i=0;i<=3;i++){
                int nx=x+dx[i],ny=y+dy[i];
                if(fw[nx][ny]==-1&&mg[x][y]!=mg[nx][ny]&&nx>=1&&ny>=1&&nx<=n&&ny<=n){
                    g.push(q{nx,ny});
                    fw[nx][ny]=1;
                }
            }
        g.pop();
    }
}
bool pd(int a,int b){
    if(flag[a][b]!=-1){
        bh=flag[a][b];
        return true;
    }
    return false;
}
int main()
{
    memset(flag,-1,sizeof(flag));
    ios::sync_with_stdio(false);
    cin>>n>>m;
    char num[1005];
    for(int i=1;i<=n;i++){
        cin>>num;
        for(int l=0;l<n;l++){
            mg[i][l+1]=num[l]-'0';
        }
    }
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        if(pd(a,b)){
            cout<<flagg[bh]<<endl;
        }else{
            numm=0;
            memset(fw,-1,sizeof(fw));
            g.push(q{a,b});
            fw[a][b]=1;
            ++qwe;
            BFS();
            cout<<numm<<endl;
        }
    }
    return 0;
}

求助大佬!


|