bfs 80分 求助

P1141 01迷宫

tyh0929 @ 2023-12-23 11:37:57

#include<bits/stdc++.h>
using namespace std;
int ax[]={1,-1,0,0};
int ay[]={0,0,1,-1};
int a[1001][1001];
bool v[1001][1001];
int n,m;
queue<int> x_;
queue<int> y_;
int bfs(int x1,int y1){
    int cnt=1;
    queue<int> x;
    queue<int> y;
    x.push(x1);
    y.push(y1);
    x_.push(x1);
    y_.push(y1);
    v[x1][y1]=1;
    while(!x.empty()){
        int ux=x.front();
        int uy=y.front();
        x.pop();
        y.pop();
        for(int i=0;i<4;i++){
            int sx=ux+ax[i];
            int sy=uy+ay[i];
            if(sy<1||sy>n||sx<1||sx>n){
                continue;
            }
            if(v[sx][sy]){
                continue;
            }
            if(a[sx][sy]==a[ux][uy]){
                continue;
            }
            x.push(sx);
            y.push(sy);
            x_.push(sx);
            y_.push(sy);
            cnt++;
            v[sx][sy]=1;
        }
    }
    return cnt;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%1d",&a[i][j]);
        }
    }
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%d\n",bfs(x,y));
        if(i==m){
            return 0;
        }
        while(!x_.empty()){
            v[x_.front()][y_.front()]=0;
            x_.pop();
            y_.pop();
        }
    }
    return 0;
}

|