# P1162 filling color (DFS)

2021-08-10 08:03:47

## P1162 Fill color （DFS）

Subject portal

The question ： to n * n The matrix will 1 Enclosed or closed 0 All become 1.

Ideas ： Obviously from the outside DFS perhaps BFS Will all 0 Just mark it .

( DFS ) AC Code ：

``````#include<bits/stdc++.h>
using namespace std;
const int N=35;
int mp[N][N],vis[N][N],n;
int d[4][2]={1,0,-1,0,0,1,0,-1};
void dfs(int x,int y){
vis[x][y]=1;
for(int i=0;i<4;i++){
int nx=x+d[i][0],ny=y+d[i][1];
if(!vis[nx][ny]&&nx>=0&&nx<=n+1&&ny>=0&&ny<=n+1&&!mp[nx][ny]){
dfs(nx,ny);
}
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) cin>>mp[i][j];
dfs(0,0);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if(!vis[i][j]&&!mp[i][j]) mp[i][j]=2;
printf(j==n?"%d\n":"%d ",mp[i][j]);
}
return 0;
}
```

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
```

( BFS )AC Code ：

``````#include<bits/stdc++.h>
using namespace std;
const int N=35;
int mp[N][N],vis[N][N],n;
int d[4][2]={1,0,-1,0,0,1,0,-1};
struct node{
int x,y;
}now,nt;
void bfs(){
now.x=0,now.y=0;
queue<node>q;
q.push(now);
while(q.size()){
now=q.front();
q.pop();
vis[now.x][now.y]=1;
for(int i=0;i<4;i++){
nt.x=now.x+d[i][0],nt.y=now.y+d[i][1];
if(nt.x>=0&&nt.x<=n+1&&nt.y>=0&&nt.y<=n+1&&!vis[nt.x][nt.y]&&!mp[nt.x][nt.y])
q.push(nt);
}
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) cin>>mp[i][j];
bfs();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if(!vis[i][j]&&!mp[i][j]) mp[i][j]=2;
printf(j==n?"%d\n":"%d ",mp[i][j]);
}
return 0;
}
```

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
```

https://chowdera.com/2021/08/20210810080205499o.html