题目分析

在这道题中，我们需要解决一个关于火星区域大气改造的模拟问题。输入的区域由多个网格组成，每个网格的状态可以是以下三种之一：

• YES：表示该网格已完成大气改造，成为宜居区。
• NO：表示该网格尚未改造，可以进行后续改造。
• NA：表示死亡区，该区域不可穿越且不参与改造。

我们的目标是判断在给定的初始网格状态下，所有的 NO 区域是否能够最终转变为 YES 区域。如果可以，输出完成改造所需的天数；如果无法完成，输出 -1。

思路概述

1. BFS（广度优先搜索）：由于每个 YES 区域能够向其上下左右的相邻 NO 区域扩散，适合使用 BFS 来模拟这种扩散过程。BFS 可以层层推进，逐步将 NO 区域转化为 YES。

2. 状态转换：在 BFS 过程中，记录每一步的天数，并在每次扩展时检查能否将 NO 区域改造为 YES。

3. 边界条件：我们需要处理边界条件，例如当输入网格中没有 NO 区域时，应该直接输出 0。

具体实现步骤

1. 输入处理：

   • 读取多行输入，直到遇到空行结束，解析成一个二维数组 grid，并将 YES、NO 和 NA 转换为 1、0 和 -1。

2. 初始化 BFS：

   • 遍历整个网格，初始化 BFS 队列，将所有 YES 的位置加入队列，并统计 NO 的总数。

3. 执行 BFS：

   • 在 BFS 中，逐层扩展当前队列中的所有 YES 区域，检查它们的上下左右四个邻居。
   • 如果邻居是 NO，则将其改为 YES，并将其位置加入队列，同时减少 NO 区域的计数。
   • 如果在某一层中所有的 NO 区域都被改造，输出所需的天数。

4. 处理输出：

   • 如果 BFS 完成后仍有 NO 区域未被改造，输出 -1。

复杂度分析

• 时间复杂度：O(n * m)，其中 n 为行数，m 为列数。每个网格最多被访问一次。
• 空间复杂度：O(n * m)，用于存储网格状态以及 BFS 队列。

问题分析

本质上，该问题可以看作一个经典的多源 BFS 问题。我们将 YES 区域视为扩散的起点（源点），NO 区域视为待扩散的目标点，而 NA 区域则视为无法穿越的障碍物。通过多源 BFS，我们可以计算从所有 YES 区域扩散至所有 NO 区域所需的最短时间，如果无法完成，则输出 -1。

Cpp

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

using namespace std;

int main() {
    vector<vector<int>> grid;
    string line;

    // 读取网格，直到输入空行
    while (getline(cin, line) && !line.empty()) {
        vector<int> row;
        size_t pos = 0;

        // 处理每行数据
        while (true) {
            size_t next_pos = line.find(" ", pos);
            string cell = line.substr(pos, next_pos - pos);
            if (cell == "YES") {
                row.push_back(1); // 转换为 1
            } else if (cell == "NO") {
                row.push_back(0); // 转换为 0
            } else {
                row.push_back(-1); // NA 区域
            }
            if (next_pos == string::npos) break; // 没有更多的空格
            pos = next_pos + 1; // 继续下一个单元格
        }
        grid.push_back(row);
    }

    int rows = grid.size();
    int cols = grid[0].size();
    queue<pair<int, int>> q;
    int totalNO = 0;

    // 初始化队列，记录所有 "YES" 的位置，并统计 "NO" 的数量
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (grid[i][j] == 1) {
                q.push({i, j});
            } else if (grid[i][j] == 0) {
                totalNO++;
            }
        }
    }

    // 如果没有 "NO" 区域，说明已经完成
    if (totalNO == 0) {
        cout << 0 << endl;
        return 0;
    }

    int days = 0;
    vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            auto [x, y] = q.front();
            q.pop();

            // 检查邻居
            for (const auto& [dx, dy] : directions) {
                int nx = x + dx;
                int ny = y + dy;
                if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && grid[nx][ny] == 0) {
                    grid[nx][ny] = 1; // 转换为宜居区域
                    q.push({nx, ny}); // 添加到队列中，待下次扩展
                    totalNO--; // 减少可改造区域的计数
                    if (totalNO == 0) {
                        cout << days + 1 << endl; // 输出转换所需的天数
                        return 0;
                    }
                }
            }
        }
        days++; // 增加天数
    }

    cout << -1 << endl; // 如果无法全部改造，输出 -1
    return 0;
}

Java

import java.util.*;

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

        // 读取网格
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine().trim();
            String[] cells = line.split(" ");
            List<Integer> row = new ArrayList<>();

            for (String cell : cells) {
                if (cell.equals("YES")) {
                    row.add(1); // 转换为 1
                } else if (cell.equals("NO")) {
                    row.add(0); // 转换为 0
                } else {
                    row.add(-1); // NA 区域
                }
            }
            grid.add(row);
        }

        int rows = grid.size();
        int cols = grid.get(0).size();
        Queue<int[]> q = new LinkedList<>();
        int totalNO = 0;

        // 初始化队列，记录所有 "YES" 的位置，并统计 "NO" 的数量
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid.get(i).get(j) == 1) {
                    q.offer(new int[]{i, j});
                } else if (grid.get(i).get(j) == 0) {
                    totalNO++;
                }
            }
        }

        // 如果没有 "NO" 区域，说明已经完成
        if (totalNO == 0) {
            System.out.println(0);
            return;
        }

        int days = 0;
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int[] pos = q.poll();
                int x = pos[0], y = pos[1];

                // 检查邻居
                for (int[] dir : directions) {
                    int nx = x + dir[0];
                    int ny = y + dir[1];
                    if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && grid.get(nx).get(ny) == 0) {
                        grid.get(nx).set(ny, 1); // 转换为宜居区域
                        q.offer(new int[]{nx, ny}); // 添加到队列中，待下次扩展
                        totalNO--; // 减少可改造区域的计数
                        if (totalNO == 0) {
                            System.out.println(days + 1); // 输出转换所需的天数
                            return;
                        }
                    }
                }
            }
            days++; // 增加天数
        }

        System.out.println(-1); // 如果无法全部改造，输出 -1
    }
}

Python

from collections import deque
import sys

def main():
    # 读取网格
    grid = []
    for line in sys.stdin:
        row = [1 if cell == "YES" else 0 if cell == "NO" else -1 for cell in line.strip().split()]
        grid.append(row)

    row = len(grid)
    column = len(grid[0])

    # 四个方向：上、下、左、右
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    q = deque()
    total_no = 0

    # 初始化队列，记录所有 "YES" 的位置，并统计 "NO" 的数量
    for i in range(row):
        for j in range(column):
            if grid[i][j] == 1:
                q.append((i, j, 0))
            elif grid[i][j] == 0:
                total_no += 1

    # 如果没有 "NO" 区域，说明已经完成
    if total_no == 0:
        print(0)
        return

    while q:
        size = len(q)
        for _ in range(size):
            x, y, days = q.popleft()

            # 检查邻居
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < row and 0 <= ny < column and grid[nx][ny] == 0:
                    grid[nx][ny] = 1  # 转换为宜居区域
                    q.append((nx, ny, days + 1))  # 添加到队列中，待下次扩展
                    total_no -= 1  # 减少可改造区域的计数
                    if total_no == 0:
                        print(days + 1)  # 输出转换所需的天数
                        return

    print(-1)  # 如果无法全部改造，输出-1

if __name__ == "__main__":
    main()

题目内容

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$

样例1

输入

YES YES NO
NO NO NO
YES NO NO

输出

2

说明

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

样例2

输入

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

输出

6

说明

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

样例3

输入

NO NA

输出

-1

说明

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

样例4

输入

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

输出

-1

说明

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