萌新不咋会bfs,感觉写不出来
by lliou @ 2023-07-18 17:19:49
你只考虑了左边,但假如包围圈的右边不在图的边缘呢,比如:
```cpp
0 0 1 1 1 0
0 1 1 0 1 0
0 1 0 0 1 0
0 1 0 0 1 0
0 1 1 1 1 0
0 0 0 0 0 0
```
就应该输出:
```cpp
0 0 1 1 1 0
0 1 1 2 1 0
0 1 2 2 1 0
0 1 2 2 1 0
0 1 1 1 1 0
0 0 0 0 0 0
```
学习宽搜了吧?这道题还是用宽搜做比较好
by Brilliant11001 @ 2023-07-18 17:26:47
```cpp
#include<iostream>
using namespace std;
int n;
int map[31][31];
int mx[4]={0,0,1,-1};
int my[4]={1,-1,0,0};
void dfs(int x,int y);
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>map[i][j];
}
}
dfs(1,1);
dfs(n,1);
dfs(1,n);
dfs(n,n);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(map[i][j]==2) cout<<0<<" ";
if(map[i][j]==0) cout<<2<<" ";
if(map[i][j]==1) cout<<1<<" ";
}
cout<<"\n";
}
}
void dfs(int x,int y){
if(map[x][y]==0){
map[x][y]=2;
for(int i=0;i<=3;i++){
if(x>=1&&x<=n&&y>=1&&y<=n&&map[x+mx[i]][y+my[i]]==0){
map[x+mx[i]][y+my[i]]=2;
dfs(x+mx[i],y+my[i]);
}
}
}
}
```
写了个神奇的深搜(?)代码,但是一直搜不全
by lliou @ 2023-08-16 11:23:16
```cpp
#include<iostream>
using namespace std;
int n;
int map[40][40];
int mx[4]={1,-1,0,0};
int my[4]={0,0,1,-1};
void dfs(int x,int y);
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>map[i][j];
}
}
dfs(1,1);
dfs(1,n);
dfs(n,1);
dfs(n,n);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(map[i][j]==2) cout<<0<<" ";
if(map[i][j]==0) cout<<2<<" ";
if(map[i][j]==1) cout<<1<<" ";
}
cout<<"\n";
}
}
void dfs(int x,int y){
if(map[x][y]==0){
map[x][y]=2;
for(int i=0;i<4;i++){
if(x>=1&&x<=n&&y>=1&&y<=n&&map[x+mx[i]][y+my[i]]==0){
dfs(x+mx[i],y+my[i]);
}
}
}
}
```
终于写了一个能正常运行的
但是48分
是不能从四个角落开始搜吗
by lliou @ 2023-08-17 09:49:44