Void-7's

洛谷P1162 填涂颜色

luogu.png

首先看下题目: P1162 填涂颜色

题解:

因为协会把题目放在搜索(dfs/bfs)下,这里我们考虑bfs的方法。

思路是这样的,我们经过观察,可以确认边缘的0永远不可能是圈内0。

所以可以先将矩阵外圈加一层0,直接从array[ 0 ][ 0 ]开始bfs,

遇到这样的元素 ( i , j ) 时:①未访问过 ②值为0 ③下标在0到n+1之间

进行如下操作:

①将vis[ i ][ j ]设置为1

②将array[ i ][ j ]设置为2或任何区别于0和1的数

③将坐标( i , j )数对作为一个元素加入队列

这样经过bfs一次调用之后,整个圈外的0都被排除了,整个矩阵剩下的0就是闭合圈0

这时候我们只要按照值的区别进行输出即可。

代码如下:

#include<bits/stdc++.h>
#include<queue>
using namespace std;

/*locations for points around (x,y)
* order:up -> right -> down -> left */
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
//record if the point is visited
int vis[32][32]={0};
//save the demanded input array
int a[32][32]={0};
//queue for bfs
queue<pair<int,int> > q;
//width of input array
int n;

void bfs(int x,int y){
    q.push(make_pair(x,y));
    vis[x][y]=1;if(!a[x][y]) a[x][y]=2;
    while(!q.empty()){
        pair<int,int> tmp=q.front();
        q.pop();
        for(int i=1;i<=4;i++){
            int rx=tmp.first+dx[i-1];
            int ry=tmp.second+dy[i-1];
            if(rx>=0&&ry>=0&&rx<=n+1&&ry<=n+1&&!a[rx][ry]&&!vis[rx][ry]){
                vis[rx][ry]=1;
                a[rx][ry]=2;
                q.push(make_pair(rx,ry));
            }
        }
    }    
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)
            scanf("%d",&a[i][j]);
    }
    bfs(0,0);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(a[i][j]==2) printf("0 ");
            else if(a[i][j]==1) printf("1 ");
            else printf("2 ");
        }
        printf("\n");
    }
    return 0;
}