P1162-填涂颜色

题目描述

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

0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1

0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1

输入格式

每组测试数据第一行一个整数n(1 le n le 30)n(1≤n≤30)
接下来n行,由0和1组成的n × n的方阵。
方阵内只有一个闭合圈,圈内至少有一个00。

输出格式

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

输入输出样例

输入 #1
6
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1
输出 #1
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1
说明/提示
1 <= n <= 30

解法思路

我最初的解法是:从地图0点遍历到(n-1)*(n-1)点,如果是没搜索过的点就从这个点调用bfs(实际bfs最多只会调用两次),在bfs中把所有0点标记出来,如果遇到墙回退,遇到边界就说明是外圈,而如果最后bfs的队列空了则说明是在圈内,把内圈全部标为2后就可以输出了。
这个解法可以ac,但是我看见题解里有一个解法很不错,代码也很精简,这里重点说一下。
思路是从下标1开始接收地图,然后搜索时从0,0点搜到n+1,n+1点,也就是模拟外面加了一圈0,用dfs从外圈的0,0点开始搜索,之所以外面加一圈就是以防起始点就是墙搜索就直接结束了。搜索时把0都改为-1(做标记,这个随意),遇见墙或边界或走过的点就回退,最后地图中还剩的0点就都是圈内了。只要在打印时,把-1点打印为0,把1点正常打印为1,把0点打印为2即可。

源码

#include<iostream>
#define maxn 35

using namespace std;

int n;
int map[maxn][maxn];
int xa[4] = { 0,0,-1,1 };
int ya[4] = { -1,1,0,0 };

void dfs(int x, int y) {
    //越界或遇墙或已染色
    if (x<0 || x>n + 1 || y<0 || y>n + 1 || map[x][y] == -1||map[x][y]==1)return;
    map[x][y] = -1;        //染色
    for (int i = 0; i < 4; i++)dfs(x + xa[i], y + ya[i]);
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> map[i][j];
    dfs(0, 0);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            if (map[i][j] == -1)cout << "0 ";
            else if (map[i][j] == 0)cout << "2 ";
            else cout << "1 ";
        cout << endl;
    }
        
    return 0;
}
本文作者:六月丶

本文链接:https://hctra.cn/index.php/archives/260/

版权声明:如无特别声明,本文即为六月'blog原创,仅代表个人观点,如要转载请务必注明文章出处。
最后修改:2019 年 10 月 11 日 11 : 18 AM
如果觉得我的文章对你有用,请随意赞赏

发表评论