当前位置:网站首页>P1162 filling color (DFS)

P1162 filling color (DFS)

2021-08-10 08:03:47 wx6110fa547fd20

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.

版权声明
本文为[wx6110fa547fd20]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/08/20210810080205499o.html