#P3226. 宜居星球改造计划(200分)
-
1000ms
Tried: 66
Accepted: 29
Difficulty: 3
所属公司 :
华为od
宜居星球改造计划(200分)
题目分析
在这道题中,我们需要解决一个关于火星区域大气改造的模拟问题。输入的区域由多个网格组成,每个网格的状态可以是以下三种之一:
YES:表示该网格已完成大气改造,成为宜居区。NO:表示该网格尚未改造,可以进行后续改造。NA:表示死亡区,该区域不可穿越且不参与改造。
我们的目标是判断在给定的初始网格状态下,所有的 NO 区域是否能够最终转变为 YES 区域。如果可以,输出完成改造所需的天数;如果无法完成,输出 -1。
思路概述
-
BFS(广度优先搜索):由于每个
YES区域能够向其上下左右的相邻NO区域扩散,适合使用 BFS 来模拟这种扩散过程。BFS 可以层层推进,逐步将NO区域转化为YES。 -
状态转换:在 BFS 过程中,记录每一步的天数,并在每次扩展时检查能否将
NO区域改造为YES。 -
边界条件:我们需要处理边界条件,例如当输入网格中没有
NO区域时,应该直接输出0。
具体实现步骤
-
输入处理:
- 读取多行输入,直到遇到空行结束,解析成一个二维数组
grid,并将YES、NO和NA转换为1、0和-1。
- 读取多行输入,直到遇到空行结束,解析成一个二维数组
-
初始化 BFS:
- 遍历整个网格,初始化 BFS 队列,将所有
YES的位置加入队列,并统计NO的总数。
- 遍历整个网格,初始化 BFS 队列,将所有
-
执行 BFS:
- 在 BFS 中,逐层扩展当前队列中的所有
YES区域,检查它们的上下左右四个邻居。 - 如果邻居是
NO,则将其改为YES,并将其位置加入队列,同时减少NO区域的计数。 - 如果在某一层中所有的
NO区域都被改造,输出所需的天数。
- 在 BFS 中,逐层扩展当前队列中的所有
-
处理输出:
- 如果 BFS 完成后仍有
NO区域未被改造,输出-1。
- 如果 BFS 完成后仍有
复杂度分析
- 时间复杂度: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
说明
右下角的区域,被周边三个死亡区挡住,无法实现改造