题解 P1162 【填涂颜色】

看到题目规模是n(1≤n≤30)即最大规模为30*30

本蒟蒻有个奇妙的想法！！

核心思路：搜索地图内除开被1包围着的0，并标注为1（即不填色）

!!!那么，我们可以从每一个边界点开始去搜索

话不多说，直接上代码

#include<iostream>
#include<cstdio>
using namespace std;
int n;
int map[35][35];
int vis[35][35];
int mov1[]={1,0,0,-1};
int mov2[]={0,1,-1,0};
void dfs(int x,int y){
     if(x<=0 || y<=0 || map[x][y]==1 || x>n || y>n || vis[x][y]==1) return;//搜索边界
     vis[x][y]=1;//只要不是被1包围着的0，都标注为不需要染色（标注为1）
     for(int i=0;i<4;i++){
        dfs(x+mov1[i],y+mov2[i]);
     }
}
void print(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(vis[i][j]==0){//只要是没有标注过的，那么都是需要染色的
                cout<<"2"<<" ";
                continue;//输出了就跳过
            }
            cout<<map[i][j]<<" ";
        }
        cout<<endl;//记得换行
    }
}
int main(){
    cin>>n;
    
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>map[i][j];
            if(map[i][j]==1) vis[i][j]=1;//地图上是1，那么vis上也是1，不需被染色（边界）
        }
    }
    /*边界都走一遍*/ 
    
    for(int i=1;i<=n;i++){
        dfs(1,i);
    }
    
    for(int j=1;j<=n;j++){
        dfs(j,1);
    }
    
    for(int i=1;i<=n;i++){
        dfs(i,n);
    }
    
    for(int j=1;j<=n;j++){
        dfs(n,j);
    } 
    
    print();//输出
    
    return 0;
}