由数字0组成的方阵中，有一任意形状闭合圈，闭合圈由数字1构成，围圈时只走上下左右4个方向。现要求把闭合圈内的所有空间都填写成2.例如：6×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的完整方阵。
1<=n<=30
解题思路:
题目让我们将被包围的0换成2,那么我们不妨将问题转化,,将所有0初始化为2,将不被包围的2换成0,转化完后便十分轻易地有了解题思路,由题知,在边界上的2一定不被1包围,那么我们用深搜求一下所有与边界上的2相连的2,更新为0,便可以求出答案.
AC代码:
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,a[35][35]; 4 bool vis[35][35]; 5 void dfs(int x,int y){//将2变成0的过程 6 if(x >= 0 && x <= n + 1 && y >= 0 && y <= n + 1){//判断是否越界 7 if(a[x][y] == 1 || a[x][y] == 0) return ;//如果是1或已经被更新过了,就跳过 8 else{ 9 a[x][y] = 0;//更新 10 dfs(x + 1, y); dfs(x - 1, y);//上下左右四个方向遍历 11 dfs(x, y + 1); dfs(x, y - 1); 12 } 13 } 14 } 15 int main() 16 { 17 cin >> n; 18 for(int i = 0;i <= n+1; i++) 19 for(int x = 0;x <= n+1; x++) { 20 if(i == 0 || x == 0) {//边界特判,如果不判,就无法一次性求出所有与边界相连的2 21 a[i][x] = 2; 22 continue; 23 } 24 if(i == n+1 || x == n+1) {//同上 25 a[i][x] = 2; 26 continue; 27 } 28 cin >> a[i][x]; 29 if(a[i][x] == 0) a[i][x] = 2;//转化问题 30 } 31 32 dfs(0,0); 33 for(int i = 1;i <= n; i++){ 34 for(int x = 1;x <= n; x++) 35 cout << a[i][x] << " "; 36 cout << endl; 37 } 38 39 40 return 0; 41 }
原文：https://www.cnblogs.com/lipeiyi520/p/10354228.html