求hack

P1162 填涂颜色

iqiqiqiqiqiqiqiq @ 2024-12-07 11:39:33

代码:

#include<iostream>
using namespace std;
int m[30][30],n;
bool at[30][30];
bool bfs(int x,int y){
    bool tmp=0,a[30][30]={0};
    int cx[900],cy[900],cnt=1;
    cx[0]=x;
    cy[0]=y;
    if(x==0||y==0||x==n-1||y==n-1)tmp=1;
    a[x][y]=1;
    while(1){
        int dx[900],dy[900],cnt2=0;
        for(int i=0;i<cnt;i++){
            dx[i]=cx[i];
            dy[i]=cy[i];
        }for(int i=0;i<cnt;i++){
            if(dx[i]+1<n&&m[dx[i]+1][dy[i]]==0&&!a[dx[i]+1][dy[i]]){
                if(dx[i]+1==n-1)tmp=1;
                a[dx[i]+1][dy[i]]=1;
                cx[cnt2]=dx[i]+1;
                cy[cnt2++]=dy[i];
            }if(dx[i]-1>=0&&m[dx[i]-1][dy[i]]==0&&!a[dx[i]-1][dy[i]]){
                if(dx[i]-1==0)tmp=1;
                a[dx[i]-1][dy[i]]=1;
                cx[cnt2]=dx[i]-1;
                cy[cnt2++]=dy[i];
            }if(dy[i]+1<n&&m[dx[i]][dy[i]+1]==0&&!a[dx[i]][dy[i]+1]){
                if(dy[i]+1==n-1)tmp=1;
                a[dx[i]][dy[i]+1]=1;
                cx[cnt2]=dx[i];
                cy[cnt2++]=dy[i]+1;
            }if(dy[i]-1>=0&&m[dx[i]][dy[i]-1]==0&&!a[dx[i]][dy[i]-1]){
                if(dy[i]-1==0)tmp=1;
                a[dx[i]][dy[i]-1]=1;
                cx[cnt2]=dx[i];
                cy[cnt2++]=dy[i]-1;
            }
        }if(cnt2==0){
            if(!tmp){
                for(int i=0;i<n;i++){
                    for(int j=0;j<n;j++){
                        if(a[i][j])m[i][j]=2;
                    }
                }
            }for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    if(a[i][j])at[i][j]=1;
                }
            }return !tmp;
        }cnt=cnt2;
    }
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>m[i][j];
        }
    }for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(m[i][j]==0&&!at[i][j]){
                if(bfs(i,j)){
                    for(int k=0;k<n;k++){
                        for(int l=0;l<n;l++){
                            cout<<m[k][l]<<' ';
                        }cout<<endl;
                    }return 0;
                }
            }
        }
    }
}

感觉不是正解,求hack

还有,如果把数据范围提到n\le50还可以AC吗?(原数据范围3ms过的)


|