跳至主要內容

【BFS】2024E-火星改造

【BFS】2024E-火星改造

题目描述与示例

本题练习地址：https://www.algomooc.com/problem/P3702

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

输出

2

说明

经过 2 个太阳日，完成宜居改造。

示例二

输入

YES NO NO NO
NO NO NO NO
NO NO NO NO
NO NO NO NO

输出

6

说明

经过 6 个太阳日，可完成改造

示例三

输入

NO NA

输出

-1

说明

无改造初始条件，无法进行改造

示例四

输入

YES NO NO YES
NO NO YES NO
NO YES NA NA
YES NO NA NO

输出

-1

说明

输出-1。右下角的区域，被周边三个死亡区挡住，无法实现改造。

解题思路

注意，本题和LC994. 腐烂的橘子完全一致。

注意到本题的一个重要条件：该区域可能存在多个宜居区，即扩散过程可能有多个起点，故我们直接使用多源BFS的模板即可完成本题目。

所谓多源BFS，无非是BFS的起点是多个起始位置，即我们的队列在初始化时，包含多个搜索起点。剩下的部分，则常规的BFS无异。

另外，由于需要判断是否能够将所有的"NO"拓展为"YES"，我们只需要提前统计"NO"的个数num_NO，在BFS过程每遇到一个"NO"就令数目-1，在最后输出时判断"NO"的个数是否大于0即可。

代码

Python

# 题目：2024E-火星改造
# 分值：200
# 作者：许老师-闭着眼睛学数理化
# 算法：多源BFS
# 代码看不懂的地方，请直接在群上提问

from collections import deque

grid = list()
# 输出的长度不确定，需要用死循环进行输入判断
while True:
    try:
        line = input()
        if len(line) == 0:
            break
        grid.append(line.split())
    except:
        break

# 获得grid两个维度上的长度
n, m = len(grid), len(grid[0])

# 初始化值为"NO"的数目
num_NO = 0

# 初始化队列q
q = deque()

# 初始化与grid大小相同的检查数组check_list，初始化其中所有元素为False，表示均未检查过
check_list = [[False] * m for _ in range(n)]

# 找到所有值为"YES"的元素的索引，存入队列q中，作为BFS起点
# 双重遍历所有索引
for i in range(n):
    for j in range(m):
        # 如果遇到"YES"
        if grid[i][j] == "YES":
            # 将该点(i, j)加入队列中
            q.append((i, j))
            # 在检查数组中将(i, j)标记为已检查过
            check_list[i][j] = True
        # 如果遇到"NO"
        elif grid[i][j] == "NO":
            # "NO"的数目+1
            num_NO += 1

# 初始化BFS的搜索层数
level = 0

while len(q) > 0:
    # 获得队列长度，为本层BFS搜索需要出队的数目
    qSize = len(q)
    # BFS搜索层数+1
    level += 1
    for _ in range(qSize):
        # 获得当前队列中的点 (x, y)
        x, y = q.popleft()
        # 遍历上下左右四个方向，为当前点的下一个点 (nx, ny)
        for nx, ny in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
            # (nx, ny)需要满足条件：
            # 1. (nx, ny) 不能越界
            # 2. (nx, ny) 尚未检查过
            # 3. (nx, ny)在grid中为"NO"
            # 才可以加入队列q，作为下一个搜索位置
            if 0 <= nx < n and 0 <= ny < m and not check_list[nx][ny] and grid[nx][ny] == "NO":
                q.append((nx, ny))              # (nx, ny)加入队列q
                check_list[nx][ny] = True       # (nx, ny)在检查数组中标记为已检查
                num_NO -= 1                     # "NO"的个数-1


# 退出循环时，如果"NO"剩余个数大于0，
# 说明还有某些"NO"无法倍拓展为"YES"，返回-1
# 否则所需要的天数为BFS搜索的层数-1
# 如果初始化level = -1，则在此处返回时直接返回level即可
print(-1 if num_NO > 0 else level-1)

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<List<String>> grid = new ArrayList<>();

        // 输入的长度不确定，使用死循环进行输入判断
        while (true) {
            try {
                String line = scanner.nextLine();
                if (line.isEmpty()) {
                    break;
                }
                List<String> row = new ArrayList<>();
                String[] elements = line.split(" ");
                row.addAll(Arrays.asList(elements));
                grid.add(row);
            } catch (Exception e) {
                break;
            }
        }

        // 获得grid两个维度上的长度
        int n = grid.size();
        int m = grid.get(0).size();

        // 初始化值为"NO"的数目
        int num_NO = 0;

        // 初始化队列q
        Queue<int[]> q = new LinkedList<>();

        // 初始化与grid大小相同的检查数组check_list，初始化其中所有元素为False，表示均未检查过
        boolean[][] checkList = new boolean[n][m];

        // 找到所有值为"YES"的元素的索引，存入队列q中，作为BFS起点
        // 双重遍历所有索引
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                // 如果遇到"YES"
                if (grid.get(i).get(j).equals("YES")) {
                    // 将该点(i, j)加入队列中
                    q.offer(new int[]{i, j});
                    // 在检查数组中将(i, j)标记为已检查过
                    checkList[i][j] = true;
                }
                // 如果遇到"NO"
                else if (grid.get(i).get(j).equals("NO")) {
                    // "NO"的数目+1
                    num_NO++;
                }
            }
        }

        // 初始化BFS的搜索层数
        int level = 0;

        while (!q.isEmpty()) {
            // 获得队列长度，为本层BFS搜索需要出队的数目
            int qSize = q.size();
            // BFS搜索层数+1
            level++;
            for (int i = 0; i < qSize; ++i) {
                // 获得当前队列中的点 (x, y)
                int[] current = q.poll();
                int x = current[0];
                int y = current[1];
                // 遍历上下左右四个方向，为当前点的下一个点 (nx, ny)
                int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
                for (int[] dir : directions) {
                    int nx = x + dir[0];
                    int ny = y + dir[1];
                    // (nx, ny)需要满足条件：
                    // 1. (nx, ny) 不能越界
                    // 2. (nx, ny) 尚未检查过
                    // 3. (nx, ny)在grid中为"NO"
                    // 才可以加入队列q，作为下一个搜索位置
                    if (nx >= 0 && nx < n && ny >= 0 && ny < m && !checkList[nx][ny] && grid.get(nx).get(ny).equals("NO")) {
                        q.offer(new int[]{nx, ny});                // (nx, ny)加入队列q
                        checkList[nx][ny] = true;                   // (nx, ny)在检查数组中标记为已检查
                        num_NO--;                                    // "NO"的个数-1
                    }
                }
            }
        }

        // 退出循环时，如果"NO"剩余个数大于0，
        // 说明还有某些"NO"无法拓展为"YES"，返回-1
        // 否则所需要的天数为BFS搜索的层数-1
        // 如果初始化level = -1，则在此处返回时直接返回level即可
        if (num_NO > 0) {
            System.out.println(-1);
        } else {
            System.out.println(level - 1);
        }
    }
}

C++

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main() {
    vector<vector<string>> grid;
    // 输入的长度不确定，使用死循环进行输入判断
    while (true) {
        string line;
        try {
            getline(cin, line);
            if (line.empty()) {
                break;
            }
            vector<string> row;
            size_t pos = 0;
            while ((pos = line.find(" ")) != string::npos) {
                row.push_back(line.substr(0, pos));
                line.erase(0, pos + 1);
            }
            row.push_back(line);
            grid.push_back(row);
        } catch (...) {
            break;
        }
    }

    // 获得grid两个维度上的长度
    int n = grid.size();
    int m = grid[0].size();

    // 初始化值为"NO"的数目
    int num_NO = 0;

    // 初始化队列q
    queue<pair<int, int>> q;

    // 初始化与grid大小相同的检查数组check_list，初始化其中所有元素为False，表示均未检查过
    vector<vector<bool>> check_list(n, vector<bool>(m, false));

    // 找到所有值为"YES"的元素的索引，存入队列q中，作为BFS起点
    // 双重遍历所有索引
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            // 如果遇到"YES"
            if (grid[i][j] == "YES") {
                // 将该点(i, j)加入队列中
                q.push({i, j});
                // 在检查数组中将(i, j)标记为已检查过
                check_list[i][j] = true;
            }
            // 如果遇到"NO"
            else if (grid[i][j] == "NO") {
                // "NO"的数目+1
                ++num_NO;
            }
        }
    }

    // 初始化BFS的搜索层数
    int level = 0;

    while (!q.empty()) {
        // 获得队列长度，为本层BFS搜索需要出队的数目
        int qSize = q.size();
        // BFS搜索层数+1
        ++level;
        for (int i = 0; i < qSize; ++i) {
            // 获得当前队列中的点 (x, y)
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            // 遍历上下左右四个方向，为当前点的下一个点 (nx, ny)
            vector<pair<int, int>> directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
            for (const auto& dir : directions) {
                int nx = x + dir.first;
                int ny = y + dir.second;
                // (nx, ny)需要满足条件：
                // 1. (nx, ny) 不能越界
                // 2. (nx, ny) 尚未检查过
                // 3. (nx, ny)在grid中为"NO"
                // 才可以加入队列q，作为下一个搜索位置
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && !check_list[nx][ny] && grid[nx][ny] == "NO") {
                    q.push({nx, ny});              // (nx, ny)加入队列q
                    check_list[nx][ny] = true;     // (nx, ny)在检查数组中标记为已检查
                    --num_NO;                      // "NO"的个数-1
                }
            }
        }
    }

    // 退出循环时，如果"NO"剩余个数大于0，
    // 说明还有某些"NO"无法拓展为"YES"，返回-1
    // 否则所需要的天数为BFS搜索的层数-1
    // 如果初始化level = -1，则在此处返回时直接返回level即可
    if (num_NO > 0){
        cout << -1 << endl;
    }
    else{
        cout << level-1 << endl;
    }
        

    return 0;
}

时空复杂度

时间复杂度：O(MN)。

空间复杂度：O(MN)。

本站内容包括机考真题解析、八股文速记、技术&行为面试指南、真实上岸经验与截图墙。
Copyright © 2025 欧弟算法