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
还有,如果把数据范围提到