为啥第四个点MLE了

P1162 填涂颜色

yushen6474 @ 2024-03-26 14:43:40

#include<iostream>
#include<stdio.h>
#include<queue>

using namespace std;

typedef pair<int,int> PII;

queue<PII> q;  //辅助队列

int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};

int n;
int map[50][50];

bool visited[50][50];

bool visited_2[50][50];

//判断该点是否在圈内 bfs
bool check(int i,int j){
    bool ans=true;

    q.push({i,j});

    while(!q.empty()){

        PII cur=q.front();
        q.pop();

        int x=cur.first;
        int y=cur.second;

        visited[x][y]=true;

        for(int k=0;k<4;k++){
            int neX=x+dx[k];
            int neY=y+dy[k];
//          cout<<neX<<" "<<neY<<endl;
            if(neX>=1&&neX<=n&&neY>=1&&neY<=n&&map[neX][neY]!=1&&!visited[neX][neY]){
                if(neX==1||neX==n||neY==1||neY==n){
                    ans=false;
                }

                q.push({neX,neY});
            }
        }

    }

    return ans;
}

void bfs(int i,int j){
    q.push({i,j});

    while(!q.empty()){

        PII cur=q.front();
        q.pop();

        int x=cur.first;
        int y=cur.second;

        visited_2[x][y]=true;
        map[x][y]=2;

        for(int k=0;k<4;k++){
            int neX=x+dx[k];
            int neY=y+dy[k];

            if(neX>=1&&neX<=n&&neY>=1&&neY<=n&&map[neX][neY]!=1&&!visited_2[neX][neY]){

                q.push({neX,neY});
            }
        }

    }
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&map[i][j]);

    bool isOver=false;

    int x,y;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(map[i][j]!=1&&!visited[i][j]){

                isOver=check(i,j);
            }

            if(isOver){
                x=i,y=j;
                break;
            }
        }
        if(isOver){
            break;
        }
    }

    bfs(x,y);

    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout<<map[i][j]<<" ";
        }cout<<endl;
    }

    return 0;       
}

|