P1162 填涂颜色

题目描述
由数字00组成的方阵中，有一任意形状闭合圈，闭合圈由数字11构成，围圈时只走上下左右44个方向。现要求把闭合圈内的所有空间都填写成22.例如：6 times 66×6的方阵（n=6n=6），涂色前和涂色后的方阵如下：

0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1

0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1

输入格式
每组测试数据第一行一个整数n(1≤n≤30)

接下来n行，由0和1组成的n×n的方阵。

方阵内只有一个闭合圈，圈内至少有一个0。

//感谢黄小U饮品指出本题数据和数据格式不一样. 已修改(输入格式)

输出格式
已经填好数字2的完整方阵。

输入输出样例
输入
6
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1

输出
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1

思路
被围墙1围起来的0不好找，所以找围墙1之外的0.
要注意：如果是dfs(1,1)开始搜，假如点(1,1)是围墙，那就会卡住，所以要在整个地图外面加一层，从dfs(0,0)开始搜。
如果可以搜到，那就将这个点设为3，最后如果点是3，就输出0，是1就输出1，是0就输出2.

#include
using namespace std;

int n;
int dx[]={1,0,0,-1};
int dy[]={0,1,-1,0};
int pos[35][35];

void dfs(int x,int y){
	if(pos[x][y]==1) return;//如果点是1，表示是墙，就返回，搜不进去了
	if(pos[x][y]==3) return;//如果=3，表示这个点已经搜过，也返回
	pos[x][y]=3;
	for(int k=0;k<4;k++){
		int tx=x+dx[k],ty=y+dy[k];
		if(tx>=0&&tx<=n+1&&ty>=0&&ty<=n+1){//注意：因为在外面加了一层，所以是0和n+1
			dfs(tx,ty);
		}
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)
			cin>>pos[i][j];
	}
	dfs(0,0);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
		//如果点是3，就输出0，是1就输出1，是0就输出2.
			if(pos[i][j]==0) cout<<2<<" ";//如果是0，就表示当时搜索时遇到了1，然后返回，所以这里的0是围墙里面的0，输出2
			else if(pos[i][j]==1) cout<<1<<" ";
			else cout<<0<<" ";
		}
		cout<					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5718573.html