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的想法属实没想到