0分过样例,求调玄关

P1141 01迷宫

wykxzhxcslhp @ 2024-10-08 22:59:11

违规紫衫

#include<bits/stdc++.h>

using namespace std;
struct node{
    int x,y;
};

int n,k,lx[5]={1,-1,0,0},ly[5]={0,0,1,-1},f[2005][2005];
bool p;
bool mp[2005][2005],is[2005][2005];
bool check(int x,int y){
    if(x>=1&&x<=n&&y>=1&&y<=n&&mp[x][y]!=p&&(!is[x][y]))return true;
    return false;
}

int bfs(int sx,int sy){
    if(sx<1||sx>n||sy<1||sy>n)return -1;
    if(f[sx][sy])return f[sx][sy];
    memset(is,false,sizeof is);
    int ans=0;
    p=!mp[sx][sy];
    queue<node>que;
    que.push({sx,sy});
    while(!que.empty()){
        int x=que.front().x,y=que.front().y;que.pop();
        if(!check(x,y))continue;
        p=mp[x][y];
        for(int i=0;i<4;i++)
            if(check(x+lx[i],y+ly[i]))
                que.push({x+lx[i],y+ly[i]});
        is[x][y]=true;
        ans++;      
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(is[i][j])f[i][j]=ans;
    return ans;
}

int main(){
    cin>>n>>k;//cout<<k<<endl;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            char a=getchar();
            while(a=='\n'||a==' ')a=getchar();
            mp[i][j]=int(a-'0');
        }   

//  for(int i=1;i<=n;i++){
//      cout<<endl;
//      for(int j=1;j<=n;j++){
//          cout<<mp[i][j]<<' ';
//      }
//  }
    for(int i=1;i<=k;i++){
        int x,y;cin>>x>>y;
        printf("%d\n",bfs(x,y));

    }
    return 0;
}

|