P1162 填涂颜色

原题如下

由数字0组成的方阵中，有一任意形状闭合圈，闭合圈由数字1构成，围圈时只走上下左右4个方向。现要求把闭合圈内的所有空间都填写成2.例如：6×6的方阵（n=6），涂色前和涂色后的方阵如下：

0 0 0 0 0 00 0 1 1 1 10 1 1 0 0 11 1 0 0 0 11 0 0 0 0 11 1 1 1 1 1

0 0 0 0 0 00 0 1 1 1 10 1 1 2 2 11 1 2 2 2 11 2 2 2 2 11 1 1 1 1 1

输入格式

每组测试数据第一行一个整数n(1≤n≤30)

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

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

输出格式

已经填好数字2的完整方阵。

输入输出样例

输入 #1复制

60 0 0 0 0 00 0 1 1 1 10 1 1 0 0 11 1 0 0 0 11 0 0 0 0 11 1 1 1 1 1

输出 #1复制

0 0 0 0 0 00 0 1 1 1 10 1 1 2 2 11 1 2 2 2 11 2 2 2 2 11 1 1 1 1 1

说明/提示

1≤n≤30

 

具体的做题想法！！！

这道题和洛谷P1506很相似，都是染色的题（搜索）。什么是染色呢，就比如有一片墙，将一个区域围起来，你要做的是把这片区域里的数字/字符全部改成其他东西。

这种题一般就要用搜索，我一般喜欢用DFS（听说大佬都是DFS加剪枝？？）。

对于这道题，它要求我们把区域内改为数字“2”。表面上看上去外围有“0”，“1”两种数字，但是我们仔细一想，这两种数字其实作用是一样的，都是起到了“墙”的作用。

所以我们果断把他们都赋值为0，写DFS即可。

ps：记得在DFS里加入回溯条件和边界条件！不然它会一直跑停不下来！

代码如下：

1 #include
      
        2 #include
       
         3 using namespace std; 4 int map[50][50],check[50][50],n; 5 int dy[5]={
    0,0,0,-1,1}; 6 int dx[5]={
    0,-1,1,0,0}; 7 void dfs(int x,int y) 8 { 9     if(x<0||x>n+1||y<0||y>n+1||check[x][y]!=0)10     return;11     check[x][y]=1;12     for(int i=1;i<=4;i++)13     {14         dfs(x+dx[i],y+dy[i]);15     }16     17 }18 int main()19 {20     cin>>n;21     for(int i=1;i<=n;i++)22     {23         for(int j=1;j<=n;j++)24         {25             cin>>map[i][j];26             if(map[i][j]==0)27             check[i][j]=0;28             else check[i][j]=2;29         }30     }31     dfs(0,0);32     for(int i=1;i<=n;i++)33     {34         for(int j=1;j<=n;j++)35         {36             if(check[i][j]==0)37             {38                 cout<<2<<' ';39             }40             else41             cout<
        
         <<' ';42         }43         cout<