小A的院子
Time Limit: 2000/1000ms (Java/Others)
Problem Description:
小A发现了一块边长为n(1≤n≤30)的正方形空地。他打算在空地上建一个闭合的院子，院子外种树。于是他在纸上画了一个只包含0和1的模拟图，用1表示院子的围墙，其余地方均为0。他想请你帮他把院子里的0全部改成2。
闭合圈不规则，由数字1构成。
（注意：围圈时只走上下左右4个方向！）
Input:
每组测试数据第一行一个整数n(1≤n≤30)。
接下来n行，由0和1组成的n×n的方阵。
方阵内只有一个闭合圈，圈内至少有一个0。
Output:
已经填好数字2的完整方阵，每行末尾有一个空格。
Sample Input:
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
Sample Output:
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.把空地方阵从(1,1)开始，dfs的时候从(0,0)开始，这样围墙外面就是连通的了，不过要注意边界要大一点，还有每次的初始化置零。2.两次dfs，第一次dfs是找到所有的0的连通分量，并判断是不是被1包围（碰到边界返回false，碰到1返回true，四个方向都返回true才是true）而被1包围的由另一个dfs修改。
解法1的代码
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int dir[][2] = {0,1,0,-1,-1,0,1,0};
int a[35][35];
int n;
void dfs(int x, int y)
{
if(x>n+2 || x<0 || y>n+2 || y<0 || a[x][y]) //边界要大一点！！
return;
a[x][y] = 2;
for(int i=0; i<4; i++){
dfs(x+dir[i][0], y+dir[i][1]);
}
}
int main()
{
while(cin >> n){
memset(a, 0, sizeof(a)); //别忘了初始化
for(int i=1; i<=n; ++i)
for(int j=1; j<=n; ++j)
scanf("%d", &a[i][j]);
dfs(0,0);
for(int i=1; i<=n; ++i){
for(int j=1; j<=n; ++j){
if(a[i][j] == 2)
cout << 0 << ' ';
if(a[i][j] == 0)
cout << 2 << ' ';
if(a[i][j] == 1)
cout << 1 << ' ';
}
cout << endl;
}
}
return 0;
}
解法2的代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int dir[][2] = {0,1,0,-1,-1,0,1,0};
int a[35][35];
bool vis[35][35];
int n;
bool dfs1(int x, int y)
{
vis[x][y] = true;
if(a[x][y] == 1) return true; //这一层返回到上一层的结果，走着走着有可能碰到1
bool flag = true;
for(int i=0; i<4; ++i){
int tx = x + dir[i][0], ty = y + dir[i][1];
if(tx>=n || tx<0 || ty>=n || ty<0)
flag = false; //一个方向碰到边界就是false，不是围墙内
else
if(!vis[tx][ty] && !dfs1(tx,ty)) //各个方向搜索，回溯，想想树
flag = false;
}
return flag;
}
void dfs2(int x, int y)
{
if(a[x][y])
return;
a[x][y] = 2;
for(int i=0; i<4; ++i)
dfs2(x+dir[i][0], y+dir[i][1]);
}
int main()
{
while(cin >> n){
memset(a, 0, sizeof(a));
memset(vis, false, sizeof(vis));
for(int i=0; i<n; ++i)
for(int j=0; j<n; ++j)
scanf("%d", &a[i][j]);
for(int i=0; i<n; ++i){
for(int j=0; j<n; ++j){
if(!vis[i][j] && !a[i][j])
if(dfs1(i, j)) dfs2(i, j);
}
}
for(int i=0; i<n; ++i){
for(int j=0; j<n; ++j)
cout << a[i][j] << ' ';
cout << endl;
}
}
return 0;
}
