P1162 填涂颜色——dfs算法

由数字000组成的方阵中，有一任意形状闭合圈，闭合圈由数字111构成，围圈时只走上下左右444个方向。现要求把闭合圈内的所有空间都填写成222.例如：6×66 \times 66×6的方阵（n=6n=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(1 \le n \le 30)n(1≤n≤30)

接下来nnn行，由000和111组成的n×nn \times nn×n的方阵。

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

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

已经填好数字222的完整方阵。
输入输出样例
输入 #1

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

输出 #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≤n≤301 \le n \le 301≤n≤30
基础的搜索题目，只要找好搜索的开端，将封闭范围内的所有零都完成搜索就好.
任何的开端一定包含：
1 1
1 0

#include <iostream>
using namespace std;

int n;
int map[30][30], next_step[][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };

bool judge(int, int); //找到开端
void dfs(int, int);

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> map[i][j];

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			if (judge(i, j))
			{
				dfs(i, j);
				for (int a = 0; a < n; a++)
				{
					cout << map[a][0];
					for (int b = 1; b < n; b++)
						cout << ' ' << map[a][b];
					cout << endl;
				}
				return 0;
			}
		}
}

bool judge(int x, int y)
{
	if (x > 0 && y > 0 && x < n && y < n)
		if (map[x][y] == 0 && map[x - 1][y] == 1 && map[x][y - 1] == 1 && map[x - 1][y - 1] == 1)
			return true;
	return false;
}

void dfs(int x, int y)
{
	map[x][y] = 2; //每当找到时就完成替换，不需要有多余的标记
	for (int i = 0; i <= 3; i++)
	{
		int tx = x + next_step[i][0];
		int ty = y + next_step[i][1];
		if (tx >= 0 && tx < n && ty >= 0 && ty < n && map[tx][ty] == 0)
			dfs(tx, ty);
	}
}