洛谷 P1162 填涂颜色

P1162 填涂颜色 - 洛谷 | 计算机科学教育新生态

题目来源

洛谷

题目内容

填涂颜色

题目描述

由数字 $0$ 组成的方阵中，有一任意形状的由数字 $1$ 构成的闭合圈。现要求把闭合圈内的所有空间都填写成 $2$。例如：$6\times 6$ 的方阵（$n=6$），涂色前和涂色后的方阵如下：

如果从某个 $0$ 出发，只向上下左右 $4$ 个方向移动且仅经过其他 $0$ 的情况下，无法到达方阵的边界，就认为这个 $0$ 在闭合圈内。闭合圈不一定是环形的，可以是任意形状，但保证闭合圈内的 $0$ 是连通的（两两之间可以相互到达）。

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

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

输入格式

每组测试数据第一行一个整数 $n(1\le n\le 30)$。

接下来 $n$ 行，由 $0$ 和 $1$ 组成的 $n\times n$ 的方阵。

方阵内只有一个闭合圈，圈内至少有一个 $0$。

输出格式

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

样例 #1

样例输入 #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

提示

对于 $100\%$ 的数据，$1\le n\le 30$。

知识点

BFS 染色法

题目思路

类似题目

和前一个类似，只需要稍微改一下输入输出就可以了
DFS 一直遍历到墙为止

AC代码

BFS

//
// Created by Jisam on 2024/7/12.
//
#include <bits/stdc++.h>
// 定义两个配对类型，用于表示坐标或其它需要成对出现的数据
#define PSI pair<string,int>
#define PII pair<int,int>
// 定义长整型的别名
#define i64 long long
// 使用标准库命名空间
using namespace std;

// 定义地图的大小
const int N = 30 + 5;
// 定义答案变量
int ans;
// 定义地图数组和访问数组
int ma[N][N];
int vis[N][N];
// 定义移动方向
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
// 定义地图的行数和列数
int n, m;

/**
 * @brief 广度优先搜索函数
 * @param x 起始点的x坐标
 * @param y 起始点的y坐标
 * 该函数使用广度优先搜索算法来探索地图，将未访问过的且不为障碍物的点标记为已访问
 */
void bfs(int x, int y) {
    queue<PII > q;
    q.push({x, y});
    while (q.size()) {
        // 取出队列头部的元素
        int tx = q.front().first;
        int ty = q.front().second;
        q.pop();
        // 如果当前位置是障碍物，则跳过
        if (ma[tx][ty] == '*') {
            continue;
        }
        // 遍历四个可能的移动方向
        for (int i = 0; i < 4; i++) {
            int fx = tx + dx[i];
            int fy = ty + dy[i];
            // 如果移动后的位置有效，并且是空白区域且未被访问过
            if (fx >= 0 && fy >= 0 && fx < n && fy < m && ma[fx][fy] == 0 && !vis[fx][fy]) {
                // 标记该位置为已访问
                ma[fx][fy] = -1;
                vis[fx][fy] = 1;
                // 将该位置加入队列继续搜索
                q.push({fx, fy});
            }
        }

    }
}

/**
 * @brief 主函数，负责读取输入和调用搜索函数
 */
void solve() {
    // 输入地图的大小
    cin >> n;
    m = n;
    // 读入地图信息
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> ma[i][j];
        }
    }
    // 从边界开始进行搜索
    for (int i = 0; i < n; i++) {
        if (!vis[i][0] && ma[i][0] != 1) bfs(i, 0);
        if (!vis[i][m] && ma[i][m] != 1) bfs(i, m);
    }
    for (int i = 0; i < m; i++) {
        if (!vis[0][i] && ma[0][i] != 1) bfs(0, i);
        if (!vis[n][i] && ma[n][i] != 1) bfs(n, i);
    }
    // 输出处理后的地图
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (ma[i][j] == -1) cout << 0;
            else if (ma[i][j] == 0) cout << 2;
            else cout << ma[i][j];
            cout << " ";
        }
        if (i != n - 1) cout << "\n";
    }

}

// 程序入口
int main() {
    // 关闭同步输入输出，提高效率
    ios::sync_with_stdio(false);
    // 解除cin与cout的绑定
    cin.tie(nullptr);
    // 调用主函数解决问题
    solve();
    // 程序正常结束
    return 0;
}

DFS

//
// Created by Administrator on 2024/7/13.
//
#include <bits/stdc++.h>
#define i64 long long // 定义长整型的别名

using namespace std;

const int N = 1e5 + 5; // 定义矩阵的大小
int ans; // 全局变量，用于存储答案
int n; // 矩阵的维度
int dx[] = {-1, 1, 0, 0}; // 定义四个方向的行移动量
int dy[] = {0, 0, -1, 1}; // 定义四个方向的列移动量

/**
 * 使用DFS算法遍历矩阵
 * @param x 当前位置的行坐标
 * @param y 当前位置的列坐标
 * @param a 二维数组表示的矩阵
 */
void dfs(int x,int y,vector<vector<int>> a){
    int i;
    // 检查当前位置是否越界或已被访问
    if(x < 0 ||  x >= n || y < 0 || y >= n ||a[x][y] != 0){
        return;
    }
    // 标记当前位置为已访问
    a[x][y] = 1;
    // 遍历四个方向的相邻位置
    for(i = 0; i < 4 ; i ++ ){
        dfs(x + dx[i],y + dy[i],a);
    }
}
/**
 * 主函数，解决具体的問題
 */
void solve() {
    cin >> n; // 输入矩阵的维度
    vector<vector<int>> a(n,vector(n,0)); // 初始化矩阵
    int x;
    // 输入矩阵的初始状态
    for(int i = 0 ; i < n ; i++){
        for(int j = 0; j < n ; j ++){
            cin >> x;
            if(x == 0) a[i][j] = 0;
            else a[i][j] = 2;
        }
    }
    // 从(0,0)位置开始进行DFS遍历
    dfs(0,0,a);

    // 输出处理后的矩阵
    for(int i = 0;  i < n ;i ++){
        for(int j = 0 ; j < n ; j ++){
            if(a[i][j] == 0) cout << 2 <<" ";
            else cout << a[i][j] <<" ";
        }
        cout << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false); // 提高速度
    cin.tie(nullptr); // 关闭输入输出同步
    solve(); // 调用解决问题的函数
    return 0
}