【华为OD-E卷 - 82 宜居星球改造计划 100分（python、java、c++、js、c）】

25-03-07 19:40

2798

13667

blog.csdn.net

id="article_content" class="article_content clearfix" style="height: 2000px; overflow: hidden;"> id="content_views" class="markdown_views prism-tomorrow-night">

【华为OD-E卷 - 宜居星球改造计划 100分（python、java、c++、js、c）】

题目

2XXX年，人类通过对火星的大气进行宜居改造分析，使得火星已在理论上具备人类宜居的条件；
由于技术原因，无法一次性将火星大气全部改造，只能通过局部处理形式；
假设将火星待改造的区域为row * column的网格，每个网格有3个值，宜居区、可改造区、死亡区，使用YES、NO、NA代替，YES表示该网格已经完成大气改造，NO表示该网格未进行改造，后期可进行改造，NA表示死亡区，不作为判断是否改造完的宜居，无法穿过；
初始化下，该区域可能存在多个宜居区，并目每个宜居区能同时在每个大阳日单位向上下左右四个方向的相邻格子进行扩散，自动将4个方向相邻的真空区改造成宜居区；
请计算这个待改造区域的网格中，可改造区是否能全部成宜居区，如果可以，则返回改造的大阳日天教，不可以则返回-1

输入描述

输入row * column个网格数据，每个网格值枚举值如下: YES，NO，NA；

样例:

YES YES NO NO NO NO NA NO YES

输出描述

可改造区是否能全部变成宜居区，如果可以，则返回改造的太阳日天数，不可以则返回-1

备注

grid[i][j]只有3种情况，YES、NO、NA

row == grid.length column == grid[i].length 1 ≤ row, column ≤ 8

用例

用例一：

输入：

YES YES NO
NO NO NO
YES NO NO
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

1
2
3

输出：

2
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

1

用例二：

输入：

YES NO NO NO
NO NO NO NO
NO NO NO NO
NO NO NO NO
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

1
2
3
4

输出：

6
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

1

用例三：

输入：

NO NA
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

1

输出：

-1
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

1

用例四：

输入：

YES NO NO YES
NO NO YES NO
NO YES NA NA
YES NO NA NO
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1
2
3
4

输出：

-1
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1

说明右下角的区域，被周边三个死亡区挡住，无法实现改造

python解法

解题思路：
这道题可以视作扩散模拟问题。具体来说，假设在一个矩阵中，每个单元格的值为 “YES” 或 “NO”（例如代表某种状态，如病人是否感染、区域是否被占领等）。我们需要计算让所有 “NO” 状态变为 “YES” 状态的最短天数，假设每次操作会将一个 “YES” 状态的周围相邻的 “NO” 状态变为 “YES”。

思路分析：
广度优先搜索（BFS）：

BFS 是一个典型的用于计算最短路径的算法，适合用来模拟从多个源节点开始的扩散过程。在本题中，多个 “YES” 状态可以作为起始点，通过 BFS 扩散，把 “NO” 变为 “YES”。
问题建模：

将每个 “YES” 单元格作为起始点放入队列。
对于每个节点，通过 BFS 扩展其相邻的 “NO” 状态。
每次扩展都会消耗一天，所以需要记录扩展的天数。
算法步骤：

遍历输入矩阵，将所有 “YES” 单元格的位置加入队列，同时统计 “NO” 的个数。
如果没有 “YES” 状态，返回 -1（无法扩散）。
如果所有的单元格一开始就是 “YES”，返回 0（无需扩散）。
使用 BFS 扩展，将相邻的 “NO” 状态变为 “YES” 并加入队列，直到队列为空或所有的 “NO” 都变为 “YES”。
最终，返回所需的天数，如果还有 “NO” 状态未被改变，返回 -1。

from collections import deque  # 引入 deque 用于队列操作

def calculate_days(grid):
    # 获取矩阵的行数和列数
    row, col = len(grid), len(grid[0])
    
    # 创建一个队列来存储所有 "YES" 的位置
    queue = deque()
    remaining = 0  # 记录 "NO" 的个数

    # 遍历矩阵，找出所有 "YES" 的位置，并统计 "NO" 的个数
    for i in range(row):
        for j in range(col):
            if grid[i][j] == "YES":
                queue.append((i, j))  # 将 "YES" 的位置加入队列
            elif grid[i][j] == "NO":
                remaining += 1  # 统计 "NO" 的个数

    # 如果没有 "YES" 单元格，无法扩散，返回 -1
    if not queue:
        return -1
    
    # 如果一开始就没有 "NO" 单元格，直接返回 0
    if remaining == 0:
        return 0

    # 初始化天数为 0
    days = 0
    # 定义 4 个方向：上、下、左、右
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    # 进行 BFS 扩展
    while queue and remaining:
        # 当前天数增加
        days += 1
        # 当前队列中所有待扩展的节点数目
        for _ in range(len(queue)):
            # 弹出队列中的一个 "YES" 单元格
            x, y = queue.popleft()
            # 检查它的 4 个相邻方向
            for dx, dy in directions:
                nx, ny = x + dx, y + dy  # 计算相邻的坐标
                # 如果相邻坐标在矩阵内，并且是 "NO"
                if 0 <= nx < row and 0 <= ny < col and grid[nx][ny] == "NO":
                    grid[nx][ny] = "YES"  # 将 "NO" 变为 "YES"
                    queue.append((nx, ny))  # 将新变为 "YES" 的单元格加入队列
                    remaining -= 1  # "NO" 的数量减少

    # 如果剩余的 "NO" 为 0，说明所有 "NO" 都变成了 "YES"，返回天数
    return days if remaining == 0 else -1

# 读取矩阵输入
matrix = []
while True:
    try:
        matrix.append(input().split())  # 每次输入一行，将其按空格分隔，存入矩阵
    except:
        break  # 输入结束时退出循环

# 调用 calculate_days 函数计算结果并打印
print(calculate_days(matrix))

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

java解法

解题思路
这道题目本质上是一个扩散问题，可以通过广度优先搜索（BFS）来模拟状态的变化。给定一个矩阵，其中每个单元格的状态是 “YES” 或 “NO”。我们需要计算从 “YES” 状态开始扩散到 “NO” 状态的最短天数，直到所有 “NO” 状态变为 “YES”。

思路分析：
矩阵的初始化：

我们首先要遍历输入的矩阵，找出所有的 “YES” 单元格并将其位置记录下来。这些 “YES” 状态的单元格就是扩散的起始点。
同时，我们需要统计 “NO” 状态的个数（toConvert），因为这些 “NO” 需要在最终变为 “YES”。
BFS 扩散过程：

对于每个 “YES” 状态的单元格，我们可以向其四个相邻的方向（上下左右）扩展。如果相邻单元格是 “NO”，那么将其变为 “YES”。
每次扩展代表了一天的过去，所以我们需要记录经过的天数。
处理边界情况：

如果没有 “YES” 状态单元格，则无法开始扩散，直接返回 -1。
如果一开始所有的单元格都是 “YES”，那么无需扩散，直接返回 0。
结果计算：

如果最终所有的 “NO” 都被成功转变为 “YES”，返回所需的天数。
如果队列为空但仍然有 “NO” 状态未被转变，说明无法完全扩散，返回 -1

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        // 创建 Scanner 对象来读取输入
        Scanner sc = new Scanner(System.in);
        // 使用 ArrayList 存储二维矩阵 grid
        ArrayList<String[]> grid = new ArrayList<>();

        // 读取每一行，直到输入结束
        while (sc.hasNextLine()) {
            grid.add(sc.nextLine().split(" "));  // 按空格分隔每一行的元素并添加到 grid
        }

        // 调用 calculateDays 方法，计算最短的天数并打印结果
        System.out.println(calculateDays(grid));
    }

    // 计算将所有 "NO" 转换为 "YES" 所需的天数
    private static int calculateDays(ArrayList<String[]> grid) {
        // 获取矩阵的行数和列数
        int rows = grid.size();
        int cols = grid.get(0).length;

        // 用于存储所有 "YES" 状态单元格的位置
        ArrayList<int[]> positions = new ArrayList<>();
        // 统计需要转换的 "NO" 的数量
        int toConvert = 0;

        // 遍历矩阵，找出 "YES" 和 "NO" 的位置
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                String cell = grid.get(i)[j];
                if ("YES".equals(cell)) {
                    positions.add(new int[]{i, j});  // 如果是 "YES"，记录其位置
                } else if ("NO".equals(cell)) {
                    toConvert++;  // 如果是 "NO"，增加计数
                }
            }
        }

        // 如果没有 "YES" 单元格，无法进行扩散，返回 -1
        if (positions.size() == 0) return -1;
        // 如果一开始矩阵中全是 "YES"，不需要扩散，直接返回 0
        if (positions.size() == rows * cols) return 0;

        // 记录扩散所需的天数
        int days = 0;
        // 定义四个方向：上、下、左、右
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        // 进行 BFS 扩散
        while (positions.size() > 0 && toConvert > 0) {
            // 用于存储当前扩散轮次的 "YES" 单元格
            ArrayList<int[]> newPositions = new ArrayList<>();

            // 遍历当前所有 "YES" 单元格，尝试扩展其相邻的 "NO"
            for (int[] pos : positions) {
                int row = pos[0], col = pos[1];
                // 遍历四个方向，向相邻单元格扩展
                for (int[] direction : directions) {
                    int newRow = row + direction[0];
                    int newCol = col + direction[1];

                    // 判断新位置是否在矩阵内，且是否是 "NO"
                    if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols
                            && "NO".equals(grid.get(newRow)[newCol])) {
                        // 将相邻的 "NO" 变为 "YES"
                        grid.get(newRow)[newCol] = "YES";
                        // 将新变为 "YES" 的位置加入新的 positions 列表中
                        newPositions.add(new int[]{newRow, newCol});
                        // 每转换一个 "NO"，减少待转换的数量
                        toConvert--;
                    }
                }
            }

            // 每扩散一次，天数增加 1
            days++;
            // 更新 positions 为新的 "YES" 位置
            positions = newPositions;
        

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

C++解法

解题思路

更新中
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1

C解法

解题思路

更新中
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1

JS解法

解题思路
这个问题的本质是一个扩散问题，类似于“腐烂”的过程，其中 “YES” 和 “NO” 表示不同的状态。我们需要计算将所有 “NO” 转换为 “YES” 所需的天数，转换是由 “YES” 状态的单元格开始，逐步扩散到相邻的 “NO” 单元格。

思路分析：
初始化矩阵：

我们首先读取输入的矩阵，并将其存储在一个二维数组 grid 中。矩阵中有两个可能的状态：“YES” 和 “NO”。
找出所有 “YES” 的位置：

我们遍历整个矩阵，记录所有 “YES” 单元格的位置，将其添加到 positions 数组中。这些 “YES” 单元格会是扩散的源头。
统计 “NO” 的数量：

同时，我们统计矩阵中 “NO” 单元格的数量，这个值存储在 toConvert 中。因为每个 “NO” 都需要通过扩散转换为 “YES”。
BFS 扩散过程：

我们使用广度优先搜索（BFS）来模拟 “YES” 状态的扩散过程。每次扩散代表一天的过去，新的 “YES” 状态会扩展到其四个相邻的 “NO” 单元格（上下左右）。
通过 BFS，可以确保我们按层次逐步扩展，并记录所需的天数。
处理边界情况：

如果没有 “YES” 单元格，则无法进行扩散，返回 -1。
如果一开始所有单元格都是 “YES”，则直接返回 0。
返回结果：

如果最终所有的 “NO” 状态都变为 “YES”，返回所需的天数。
如果队列为空，但仍然有 “NO” 状态没有变为 “YES”，则返回 -1，表示无法完全扩散

const readline = require("readline");

// 创建一个 readline 接口，用于读取输入
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

// 用于存储输入的矩阵
const input = [];
rl.on("line", (line) => {
    input.push(line); // 将每一行输入存入 input 数组
}).on("close", () => {
    // 处理输入数据，转换成二维数组 grid
    const grid = input.map(line => line.split(" "));  // 按空格分割每行数据
    // 计算并输出转换所需的最短天数
    console.log(calculateDays(grid));
});

// 计算将所有 "NO" 状态变为 "YES" 状态所需的天数
function calculateDays(grid) {
    const rows = grid.length;  // 获取矩阵的行数
    const cols = grid[0].length;  // 获取矩阵的列数

    let positions = [];  // 用于记录所有 "YES" 单元格的位置
    let toConvert = 0;  // 用于统计需要转换的 "NO" 数量

    // 遍历矩阵，记录 "YES" 的位置，并统计 "NO" 的数量
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            const cell = grid[i][j];
            if (cell === "YES") {
                positions.push([i, j]);  // 记录 "YES" 单元格的位置
            } else if (cell === "NO") {
                toConvert++;  // 统计 "NO" 单元格的数量
            }
        }
    }

    // 如果没有 "YES" 状态，无法进行扩散，返回 -1
    if (positions.length === 0) return -1;
    // 如果一开始所有单元格都是 "YES"，无需扩散，直接返回 0
    if (positions.length === rows * cols) return 0;

    let days = 0;  // 记录扩散所需的天数
    // 定义四个方向：上、下、左、右
    const directions = [
        [-1, 0], [1, 0], [0, -1], [0, 1]
    ];

    // 进行广度优先搜索（BFS）扩散过程
    while (positions.length > 0 && toConvert > 0) {
        let newPositions = [];  // 用于存储本轮扩散后变成 "YES" 的单元格

        // 遍历当前所有 "YES" 单元格
        for (let pos of positions) {
            const [row, col] = pos;  // 获取当前 "YES" 单元格的坐标

            // 遍历四个方向，尝试扩展到相邻的 "NO" 单元格
            for (let [dRow, dCol] of directions) {
                const newRow = row + dRow;  // 计算相邻单元格的新行号
                const newCol = col + dCol;  // 计算相邻单元格的新列号

                // 判断新位置是否在矩阵内，并且是否是 "NO"
                if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && grid[newRow][newCol] === "NO") {
                    grid[newRow][newCol] = "YES";  // 将 "NO" 转换为 "YES"
                    newPositions.push([newRow, newCol]);  // 将新变为 "YES" 的位置加入新列表
                    toConvert--;  // 每转换一个 "NO"，减少待转换的数量
                }
            }
        }

        days++;  // 每扩散一次，天数增加 1
        positions = newPositions;  // 更新 positions 为本轮扩散后的 "YES" 位置
    }

    // 如果所有的 "NO" 都变成了 "YES"，返回天数；否则返回 -1
    return toConvert === 0 ? days : -1;
}

 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

注意：

如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏

注：本文转载自blog.csdn.net的CodeClimb的文章"https://blog.csdn.net/CodeClimb/article/details/145064939"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。

复制链接

发表评论

注册

评论记录：

未查询到任何数据！