5号点MLE求条

P1162 填涂颜色

Wavestars @ 2024-10-21 12:43:18

}
#include <bits/stdc++.h>
using namespace std;
int n;
int mp[33][33];
int mode=2; 
short dx[5]={0,0,-1,0,1};
short dy[5]={0,-1,0,1,0};
struct node{
    int x,y;
};
queue<node> q;
void init(){
    for(int i=0;i<=n+1;i++){
        mp[0][i]=-1;
        mp[n+1][i]=-1;
        mp[i][0]=-1;
        mp[i][n+1]=-1;
    }
}
void print(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(mp[i][j]==-2) printf("0 ",mp[i][j]);
            else printf("%d ",mp[i][j]);
        }
        printf("\n");
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&mp[i][j]);
    init();
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){
        node a;
        a.x=i,a.y=j;
        if(mp[i][j]==0) q.push(a);
        while(!q.empty()){
            switch(mode){
                case 2:
                    mp[q.front().x][q.front().y]=2;
                    for(int k=1;k<=4;k++){
                        if(mp[q.front().x+dx[k]][q.front().y+dy[k]]==-1){
                            a.x=q.front().x,a.y=q.front().y;
                            mode=-2;
                            while(!q.empty()) q.pop();
                            q.push(a);
                            break;
                        }
                        if(!mp[q.front().x+dx[k]][q.front().y+dy[k]]){
                            a.x=q.front().x+dx[k], a.y=q.front().y+dy[k];
                            q.push(a);
                        }
                    }
                    if(mode==-2) break;
                    if(!q.empty()) q.pop();
                    break;
                case -2:
                    mp[q.front().x][q.front().y]=-2;
                    for(int k=1;k<=4;k++){
                        if(mp[q.front().x+dx[k]][q.front().y+dy[k]]==2 || mp[q.front().x+dx[k]][q.front().y+dy[k]]==0){
                            a.x=q.front().x+dx[k], a.y=q.front().y+dy[k];
                            q.push(a);
                        }
                    }
                    if(!q.empty()) q.pop();
                    break;
                default:
                    cout<<"RE"<<endl;
                    break;
            }
        }
        mode=2;
    }
    print();
    return 0;
}

by chenbs @ 2024-10-21 13:04:58

#include<bits/stdc++.h>
using namespace std;
int n,a[35][35],vis[35][35];
const int d[4][2]= {{-1,0},{1,0},{0,-1},{0,1}};
int bfs(int mode, int i, int j) {
    memset(vis,0,sizeof vis);
    queue<pair<int,int> >q;
    q.push({i,j});
    while(!q.empty()) {
        int x=q.front().first, y=q.front().second;
        q.pop();

        if(vis[x][y]) continue;
        vis[x][y]=1;

        for(int i=0; i<4; i++)
            if(a[x+d[i][0]][y+d[i][1]] == 0)
                q.push({x+d[i][0],y+d[i][1]});
        if(x==1 || y==1 || x==n || y==n) return 0;
        if(mode) a[x][y]=2;
    }
    return 1;
}
int main() {
    cin>>n;
    for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) cin>>a[i][j];
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            if(a[i][j]==1) continue;
            if(bfs(0,i,j)) bfs(1,i,j);
        }
    }
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) cout<<a[i][j]<<' ';
        cout<<'\n';
    }
}

by chenbs @ 2024-10-21 13:05:28

bfs 不用写这么长啊


by SnowZ @ 2024-11-20 17:35:05

@chenbs感谢大佬,这个mode的想法属实没想到


|