P1162 填涂颜色 （DFS）

题目传送门

题意：给n * n矩阵将1围住的闭圈的0全变为1.

思路：显然从外围一圈DFS或者BFS将所有0标记即可。

( DFS ) AC代码：

#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;
}

( BFS )AC代码：

#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;
}