Specter_LiZN @ 2024-08-31 16:18:51
#include <bits/stdc++.h>
#define f(i,a,b) for (int i=a;i<=b;i++)
#define LL undefined long long
#define Shion cout << "Shion is too poor to print that." << endl
const int Miku=0x39c5bb;
using namespace std;
int n,in[35][35];
bool flags[35][35],fin;
const int dx[5]={Miku,0,0,1,-1};
const int dy[5]={Miku,1,-1,0,0};
bool walk(int x,int y,int drct){
int xx=x+dx[drct];
int yy=y+dy[drct];
if(xx>0&&yy>0&&xx<=n&&yy<=n)
if(in[xx][yy]==0)
walk(xx,yy,drct);
else
return 1;
else
return 0;
}
void dfs(int x,int y,bool tp){
if(!tp){
if(!in[x][y]){
int flag=0;
f(i,1,4){
if(walk(x,y,i))
flag++;
}
if(flag==4){
flags[x][y]=1;
fin=1;
f(i,1,4){
int xx=x+dx[i];
int yy=y+dy[i];
dfs(xx,yy,1);
}
}
}
}
else{
if(!in[x][y]&&x>0&&y>0&&x<=n&&y<=n){
flags[x][y]=1;
f(i,1,4){
int xx=x+dx[i];
int yy=y+dy[i];
dfs(xx,yy,1);
}
}
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
f(i,1,n)
f(j,1,n)
cin>>in[i][j];
f(i,1,n)
f(j,1,n){
if(!fin)
dfs(i,j,0);
else
break;
}
f(i,1,n){
f(j,1,n){
if(flags[i][j])
cout<<"2 ";
else
cout<<in[i][j]<<" ";
}
cout<<'\n';
}
return 0;
Shion;
}
当事人在写的时候（感觉自己）思路清晰
而实际上：
1.return value 3221225725
2.缩进大小调为2格导致只有聪明的人才看得懂（bushi
3.超烂的思路以及顾及沉没成本的浪子不回头想法
4.一点注释没有（平生讨厌两种人.jpg）
所以真的希望有神犇指点一下
by Specter_LiZN @ 2024-08-31 16:19:36
哦对了 还有不知所以的宏
by CQ天神 @ 2024-08-31 16:21:12
@Specter_LiZN 我写了两份代码，你可以参考一下 bfs:
#include <bits/stdc++.h>
using namespace std;
int mp[31][31];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int n;
queue<int> q;
void bfs(int x,int y){
int x1,x2,y1,y2;
q.push(x);
q.push(y);
mp[x][y]=2;
while(!q.empty()){
x1=q.front();
q.pop();
y1=q.front();
q.pop();
for(int i=0;i<4;i++){
x2=x1+dx[i];
y2=y1+dy[i];
if(x2>=0&&x2<=n+1&&y2>=0&&y2<=n+1&&mp[x2][y2]==0){
q.push(x2);
q.push(y2);
mp[x2][y2]=2;
}
}
}
return;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>mp[i][j];
}
}
bfs(0,0);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cout<<(mp[i][j]==0?2:(mp[i][j]==1?1:0))<<' ';
}
cout<<endl;
}
return 0;
}dfs:
#include <bits/stdc++.h>
using namespace std;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int a[1001][1001],n;
bool vis[1001][1001];
void dfs(int x,int y){
if(x<0||x>n+1||y<0||y>n+1||vis[x][y]!=0) return ;
vis[x][y]=1;
for(int i=0;i<4;i++) dfs(x+dx[i],y+dy[i]);
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
if(a[i][j]==0) vis[i][j]=0;
else vis[i][j]=2;
}
}
dfs(0,0);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(vis[i][j]==0) cout<<2<<" ";
else cout<<a[i][j]<<" ";
}
cout<<endl;
}
return 0;
} by Yxy7952 @ 2024-08-31 16:22:48
@Specter_LiZN
仅作参考，但这道题应该只能用bfs过吧
by Specter_LiZN @ 2024-08-31 16:35:19
@CQ天神
感谢dalao！我再看看
by Specter_LiZN @ 2024-08-31 16:37:17
@yixingyou
的确是 但这个思路实际上哪种优先搜索都不算（好像
我想的是找到第一个可以被涂色的‘0’
by LiDingguang @ 2024-08-31 22:33:41
因为方阵内只有一个闭合圈，所以只需先遍历找到一个在闭合圈内的0，再深搜，把闭合圈里所有0变成2即可。
#include<bits/stdc++.h>
using namespace std;
int n;
int a[31][31];
bool dfs[31][31];
bool dfs1(int x,int y){
dfs[x][y]=1;
if(x==0||x==n-1||y==0||y==n-1){
return 1;
}
if(dfs[x-1][y]==0&&a[x-1][y]==0&&dfs1(x-1,y)==1||dfs[x+1][y]==0&&a[x+1][y]==0&&dfs1(x+1,y)==1||dfs[x][y-1]==0&&a[x][y-1]==0&&dfs1(x,y-1)==1||dfs[x][y+1]==0&&a[x][y+1]==0&&dfs1(x,y+1)==1){
return 1;
}
return 0;
}
void dfs2(int x,int y){
if(a[x-1][y]==0){
a[x-1][y]=2;
dfs2(x-1,y);
}
if(a[x+1][y]==0){
a[x+1][y]=2;
dfs2(x+1,y);
}
if(a[x][y-1]==0){
a[x][y-1]=2;
dfs2(x,y-1);
}
if(a[x][y+1]==0){
a[x][y+1]=2;
dfs2(x,y+1);
}
return ;
}
int main(){
cin>>n;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>a[i][j];
}
}
for(int i=1;i<n-1;i++){
for(int j=1;j<n-1;j++){
if(a[i][j]==0&&dfs1(i,j)==0){
dfs2(i,j);
a[i][j]=2;
for(int ii=0;ii<n;ii++){
for(int jj=0;jj<n;jj++){
cout<<a[ii][jj]<<' ';
}
cout<<endl;
}
return 0;
}
}
}
return 0;
}