设为首页 加入收藏

TOP

题解 P1162 【填涂颜色】
2019-06-08 00:08:04 】 浏览:19
Tags:题解 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;
}



编程开发网
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇程序填空题(一) 下一篇简单而粗暴的方法画任意阶数Bezie..

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(217) }