洛谷p1162填涂颜色（dfs写法）

这道题本是放在试炼场bfs里的，但是我觉得dfs好写些

所以就用dfs过了

题目如下

题目描述

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

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

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

输出格式：

已经填好数字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

思路：

先把读到的0都变为2

然后从外围dfs

把遇到的2变为0

输出时遇到2变为0遇到0变为2

代码如下：

#include
#include
#include
#include 
using namespace std;
const int maxn = 105;
int s[maxn][maxn];
int a[maxn][maxn];
int n;
int fx[6]={0,-1,1,0,0};
int fy[6]={0,0,0,-1,1};
void dfs(int x,int y){if(x < 0 || x > n || y < 0|| y > n ||a[x][y] != 0) return;a[x][y]=1;for(int i = 1;i <= 4;i++) dfs(x+fx[i],y+fy[i]);
} 
int main(){cin>>n;for(int i = 1;i <= n;i++)for(int j = 1;j <= n;j++){cin>>s[i][j];if(s[i][j] != 0) a[i][j] = 2;}for(int i = 1;i <= n;i++){     //从边上的每个位置都bfs防止有特殊数据dfs(1,i);dfs(i,1);dfs(n,i);dfs(i,n);}//cout<