(B卷,200分)- 宜居星球改造计划（Java & JS & Python & 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

用例

题目解析

本题是图的多源BFS的经典题，解析可以参考：

注意本题没有输入截止条件，因此，我将输入空行作为输入截止条件。

2023.09.17

根据考友反馈：

Java和JS的可以使用空行作为输入截止条件，Python的貌似不可以。

Java考友反馈

JS考友反馈

Python考友反馈

关于无输入截止条件的ACM输入获取，可以参考下我这边篇博客

华为OD机试关于无输入截止条件的ACM输入逻辑_伏城之外的博客-CSDN博客

下面我将代码输入获取更新为最通用的处理方式，即上面博客第三种综合处理方式。

Java算法源码

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

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    ArrayList<String[]> matrix = new ArrayList<>();

    // 假设存在空行作为输入截止条件
    //    while (sc.hasNextLine()) {
    //      String line = sc.nextLine();
    //      if ("".equals(line)) {
    //        System.out.println(getResult(matrix));
    //        break;
    //      } else {
    //        matrix.add(line.split(" "));
    //      }
    //    }

    // 没有空行作为输入截止条件时
    while (sc.hasNextLine()) {
      matrix.add(sc.nextLine().split(" "));
    }

    System.out.println(getResult(matrix));
  }

  private static int getResult(ArrayList<String[]> matrix) {
    int row = matrix.size();
    int col = matrix.get(0).length;

    // 记录宜居取坐标位置
    ArrayList<int[]> queue = new ArrayList<>();

    // 记录可改造区数量
    int need = 0;

    for (int i = 0; i < row; i++) {
      for (int j = 0; j < col; j++) {
        String val = matrix.get(i)[j];
        switch (val) {
          case "YES":
            queue.add(new int[] {i, j});
            break;
          case "NO":
            need++;
            break;
        }
      }
    }

    // 如果没有宜居区，则无法改造，直接返回-1
    if (queue.size() == 0) return -1;
    // 如果全是宜居区，则无需改造，直接返回0
    if (queue.size() == row * col) return 0;

    // 记录花费的天数
    int day = 0;

    // 上，下，左，右四个方向的偏移量
    int[][] offsets = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    // 图的多源BFS模板
    while (queue.size() > 0 && need > 0) {
      ArrayList<int[]> newQueue = new ArrayList<>();

      for (int[] pos : queue) {
        int x = pos[0], y = pos[1];
        for (int[] offset : offsets) {
          // 上，下，左，右四个方向扩散
          int newX = x + offset[0];
          int newY = y + offset[1];

          // 如果新位置没有越界，且为NO，则可以被改造
          if (newX >= 0
              && newX < row
              && newY >= 0
              && newY < col
              && "NO".equals(matrix.get(newX)[newY])) {
            matrix.get(newX)[newY] = "YES";
            newQueue.add(new int[] {newX, newY});
            need--;
          }
        }
      }

      day++;
      queue = newQueue;
    }

    if (need == 0) return day;
    else return -1;
  }
}

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
  const matrix = [];

  // 假设存在空行作为输入截止条件
  // while (true) {
  //   const line = await readline();

  //   if (line != "") {
  //     matrix.push(line.split(" "));
  //   } else {
  //     break;
  //   }
  // }

  // 没有空行作为输入截止条件时
  while (true) {
    try {
      matrix.push((await readline()).split(" "));
    } catch (error) {
      break;
    }
  }

  console.log(getResult(matrix));
})();

function getResult(matrix) {
  const row = matrix.length;
  const col = matrix[0].length;

  // 记录宜居取坐标位置
  let queue = [];
  // 记录可改造区数量
  let need = 0;

  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
      switch (matrix[i][j]) {
        case "YES":
          queue.push([i, j]);
          break;
        case "NO":
          need++;
          break;
      }
    }
  }

  // 如果没有宜居区，则无法改造，直接返回-1
  if (queue.length == 0) return -1;
  // 如果全是宜居区，则无需改造，直接返回0
  if (queue.length == row * col) return 0;

  // 记录花费的天数
  let day = 0;
  // 上，下，左，右四个方向的偏移量
  const offsets = [
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1],
  ];

  // 图的多源BFS模板
  while (queue.length > 0 && need > 0) {
    const newQueue = [];

    for (let [x, y] of queue) {
      for (let offset of offsets) {
        // 上，下，左，右四个方向扩散
        const newX = x + offset[0];
        const newY = y + offset[1];

        // 如果新位置没有越界，且为NO，则可以被改造
        if (
          newX >= 0 &&
          newX < row &&
          newY >= 0 &&
          newY < col &&
          "NO" == matrix[newX][newY]
        ) {
          matrix[newX][newY] = "YES";
          newQueue.push([newX, newY]);
          need--;
        }
      }
    }

    day++;
    queue = newQueue;
  }

  if (need == 0) return day;
  else return -1;
}

Python算法源码

# 算法入口
def getResult(matrix):
    row = len(matrix)
    col = len(matrix[0])

    # 记录宜居取坐标位置
    queue = []
    # 记录可改造区数量
    need = 0

    for i in range(row):
        for j in range(col):
            if matrix[i][j] == "YES":
                queue.append([i, j])
            elif matrix[i][j] == "NO":
                need += 1

    # 如果没有宜居区，则无法改造，直接返回-1
    if len(queue) == 0:
        return -1
    # 如果全是宜居区，则无需改造，直接返回0
    elif len(queue) == row * col:
        return 0

    # 记录花费的天数
    day = 0
    # 上，下，左，右四个方向的偏移量
    offsets = ((-1, 0), (1, 0), (0, -1), (0, 1))

    # 图的多源BFS模板
    while len(queue) > 0 and need > 0:
        newQueue = []

        for x, y in queue:
            for offsetX, offsetY in offsets:
                # 上，下，左，右四个方向扩散
                newX = x + offsetX
                newY = y + offsetY

                # 如果新位置没有越界，且为NO，则可以被改造
                if row > newX >= 0 and col > newY >= 0 and matrix[newX][newY] == "NO":
                    matrix[newX][newY] = "YES"
                    newQueue.append([newX, newY])
                    need -= 1

        day += 1
        queue = newQueue

    if need == 0:
        return day
    else:
        return -1


# 输入获取
matrix = []

# 假设存在空行作为输入截止条件
# while True:
#     line = input()
#     if line == "":
#         print(getResult(matrix))
#         break
#     else:
#         matrix.append(line.split())

# 没有空行作为输入截止条件时
while True:
    try:
        matrix.append(input().split())
    except:
        break
print(getResult(matrix))

C算法源码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_SIZE 8

typedef struct ListNode {
    int ele;
    struct ListNode *next;
} ListNode;

typedef struct {
    int size;
    ListNode *head;
    ListNode *tail;
} LinkedList;

LinkedList *new_LinkedList();
void addLast_LinkedList(LinkedList *link, int ele);

int getResult(int row, int col, int matrix[MAX_SIZE][MAX_SIZE]);

int main() {
    int matrix[MAX_SIZE][MAX_SIZE];

    int row = 0;
    int col = 0;

    char s[1000];
    while(gets(s)) {
        // 本地测试可以开启此行
        // if(strlen(s) == 0) break;

        col = 0;
        char* token = strtok(s, " ");
        while(token != NULL) {
            // YES 简化为 0, NO 简化为 1, NA 简化为 2
            if(strcmp("YES", token) == 0) {
                matrix[row][col] = 0;
            } else if(strcmp("NO", token) == 0) {
                matrix[row][col] = 1;
            } else {
                matrix[row][col] = 2;
            }

            token = strtok(NULL, " ");
            col++;
        }
        row++;
    }

    printf("%dn", getResult(row, col, matrix));

    return 0;
}

int getResult(int row, int col, int matrix[MAX_SIZE][MAX_SIZE]) {
    // 记录宜居区坐标位置
    LinkedList *queue = new_LinkedList();

    // 记录可改造区数量
    int need = 0;

    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            switch (matrix[i][j]) {
                case 0:
                    addLast_LinkedList(queue, i * col + j);
                    break;
                case 1:
                    need++;
                    break;
            }
        }
    }

    // 如果没有宜居区，则无法改造，直接返回-1
    if (queue->size == 0) return -1;
    // 如果全是宜居区，则无需改造，直接返回0
    if (queue->size == row * col) return 0;

    // 记录花费的天数
    int day = 0;

    // 上，下，左，右四个方向的偏移量
    int offsets[4][2] = {{-1, 0},
                         {1,  0},
                         {0,  -1},
                         {0,  1}};

    // 图的多源BFS模板
    while (queue->size > 0 && need > 0) {
        LinkedList *newQueue = new_LinkedList();

        ListNode *cur = queue->head;
        while (cur != NULL) {
            int x = cur->ele / col;
            int y = cur->ele % col;

            // 上，下，左，右四个方向扩散
            for (int i = 0; i < 4; i++) {
                int newX = x + offsets[i][0];
                int newY = y + offsets[i][1];

                // 如果新位置没有越界，且为NO，则可以被改造
                if (newX >= 0 && newX < row && newY >= 0 && newY < col && matrix[newX][newY]== 1) {
                    matrix[newX][newY] = 0;
                    addLast_LinkedList(newQueue, newX * col + newY);
                    need--;
                }
            }

            cur = cur->next;
        }

        day++;
        queue = newQueue;
    }

    if (need == 0) {
        return day;
    } else {
        return -1;
    }
}

LinkedList *new_LinkedList() {
    LinkedList *link = (LinkedList *) malloc(sizeof(LinkedList));

    link->size = 0;
    link->head = NULL;
    link->tail = NULL;

    return link;
}

void addLast_LinkedList(LinkedList *link, int ele) {
    ListNode *node = (ListNode *) malloc(sizeof(ListNode));

    node->ele = ele;
    node->next = NULL;

    if (link->size == 0) {
        link->head = node;
        link->tail = node;
    } else {
        link->tail->next = node;
        link->tail = node;
    }

    link->size++;
}