题目描述
由数字0组成的方阵中，有一任意形状闭合圈，闭合圈由数字1构成，围圈时只走上下左右4个方向。现要求把闭合圈内的所有空间都填写成2.例如：6 × 6的方阵（n = 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 le n le 30)n(1≤n≤30) 接下来n行，由0和1组成的n × n的方阵。 方阵内只有一个闭合圈，圈内至少有一个00。
输出格式
已经填好数字2的完整方阵。
输入输出样例
输入 #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 <= 30
解法思路
我最初的解法是：从地图0点遍历到(n-1)*(n-1)点，如果是没搜索过的点就从这个点调用bfs(实际bfs最多只会调用两次),在bfs中把所有0点标记出来，如果遇到墙回退，遇到边界就说明是外圈，而如果最后bfs的队列空了则说明是在圈内，把内圈全部标为2后就可以输出了。 这个解法可以ac，但是我看见题解里有一个解法很不错，代码也很精简，这里重点说一下。 思路是从下标1开始接收地图，然后搜索时从0，0点搜到n 1,n 1点，也就是模拟外面加了一圈0,用dfs从外圈的0,0点开始搜索，之所以外面加一圈就是以防起始点就是墙搜索就直接结束了。搜索时把0都改为-1(做标记，这个随意),遇见墙或边界或走过的点就回退，最后地图中还剩的0点就都是圈内了。只要在打印时，把-1点打印为0,把1点正常打印为1，把0点打印为2即可。
源码
代码语言：javascript复制#include<iostream>
#define maxn 35
using namespace std;
int n;
int map[maxn][maxn];
int xa[4] = { 0,0,-1,1 };
int ya[4] = { -1,1,0,0 };
void dfs(int x, int y) {
//越界或遇墙或已染色
if (x<0 || x>n 1 || y<0 || y>n 1 || map[x][y] == -1||map[x][y]==1)return;
map[x][y] = -1; //染色
for (int i = 0; i < 4; i )dfs(x xa[i], y ya[i]);
}
int main() {
cin >> n;
for (int i = 1; i <= n; i )
for (int j = 1; j <= n; j )
cin >> map[i][j];
dfs(0, 0);
for (int i = 1; i <= n; i ) {
for (int j = 1; j <= n; j )
if (map[i][j] == -1)cout << "0 ";
else if (map[i][j] == 0)cout << "2 ";
else cout << "1 ";
cout << endl;
}
return 0;
}
