P1162 填涂颜色

NOI

 2019/07/07 

如果被包围的部分没什么特点，那么就可以看看其他部分有没有什么特点，本题中就是可以从外围开始搜索，搜到墙就停下，最后没被搜到的部分就是被墙包围的部分
为了防止外围起点就是墙，或者是外围的0被墙分为好几部分导致我们无法搜索到被分割的部分，可以多开一圈数组，使得外围相互连接起来，确保不被包围的0一定可以被搜到

#include<iostream>
#include<cstdio>
using namespace std;
int n,dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};bool graph[32][32],vis[32][32];
///graph 记录这个图原来是0还是1（空还是墙），vis记录被没被访问过
///注意这两个数组都是开的32（数据是1~30，本来开31就够了）保证了外面又一圈0，也就是最外面的一圈都是联通的，避免了第一个点1,1就是墙导致循环循环不下去的情况，也避免了一堵墙把中间全部堵死，只扫了墙左边的0，没扫同在墙外但在墙右边的0的情况
void dfs(int, int);
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>graph[i][j];

    dfs(0,0);

    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(vis[i][j]) cout<<"0 ";///如果访问过，那么一定是墙外的0
            else
                if(graph[i][j]) cout<<"1 ";///输入时原本是墙，那么它还是墙（这一句可以和上面那一句互换位置）
            else cout<<"2 ";///及没被访问过，输入时也不是墙，那么肯定是被包围在里面的0
        }
        cout<<endl;
    }

    return 0;
}
void dfs(int x, int y)
{
    if( x<0 | x>n+1 | y<0 | y>n+1 | graph[x][y] | vis[x][y] )
    ///如果1.越界（注意是 <0|>n+1 这里可以看出来我们多开了一圈0在原输入外面）
    ///2.是墙|被访问过 那么不做操作
        return;
    vis[x][y]=true;
    for(int i=0;i<4;i++)
        dfs(x+dir[i][0],y+dir[i][1]);
}

Author：Yao Lirong

Link：https://yao-lirong.github.io/blog/2019-07-07-P1162-%E5%A1%AB%E6%B6%82%E9%A2%9C%E8%89%B2/

Publish date：July 7th 2019, 12:00:00 am

Update date：October 7th 2019, 5:02:30 am

License：本文采用 Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0) 进行许可

Next Post

Value Representation, Hashing, and Generics
Previous Post

P1141 01迷宫

CATALOG