(C卷,200分)- 污染水域（Java & JS & Python & C）

题目描述

输入一行字符串，字符串可转换为N*N的数组，数组可认为是一个水域，判断多少天后，水域被全部污染。
数组中只有0和1，0表示纯净，1表示污染，每天只可污染上下左右的水域，如果开始全部被污染，或永远无法污染，则返回-1。

输入描述

无

输出描述

无

用例

题目解析

本题可以采用图的多源BFS来解决。图的多源BFS实现关键点在于理解queue的作用。解析可以参考：

JavaScript算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

rl.on("line", (line) => {
  const nums = line.split(",").map(Number);

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

function getResult(nums) {
  // 矩阵 n x n
  const n = Math.sqrt(nums.length);

  // 未污染区域数量
  let total = nums.length;

  // 矩阵
  const matrix = new Array(n).fill(0).map(() => new Array(n));

  // BFS队列
  let queue = [];

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      matrix[i][j] = nums[i * n + j];

      if (matrix[i][j] === 1) {
        queue.push([i, j]);
        total--;
      }
    }
  }

  if (queue.length === 0 || queue.length === nums.length) {
    return -1;
  }

  // 上下左右方位偏移量
  const offsets = [
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1],
  ];

  // 扩散天数
  let day = 0;

  while (queue.length > 0 && total > 0) {
    const newQueue = [];

    for (const [i, j] of queue) {
      for (const [offsetI, offsetJ] of offsets) {
        const newI = i + offsetI;
        const newJ = j + offsetJ;

        if (
          newI >= 0 &&
          newI < n &&
          newJ >= 0 &&
          newJ < n &&
          matrix[newI][newJ] == 0
        ) {
          matrix[newI][newJ] = 1;
          newQueue.push([newI, newJ]);
          total--;
        }
      }
    }

    queue = newQueue;
    day++;
  }

  return day;
}

Java算法源码

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
  // 输入获取
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int[] nums = Arrays.stream(sc.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();
    System.out.println(getResult(nums));
  }

  // 算法入口
  public static int getResult(int[] nums) {
    int n = (int) Math.sqrt(nums.length);

    LinkedList<int[]> queue = new LinkedList<>();
    int[][] matrix = new int[n][n];
    int total = nums.length;

    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        matrix[i][j] = nums[i * n + j];

        if (matrix[i][j] == 1) {
          queue.add(new int[] {i, j});
          total--;
        }
      }
    }

    if (queue.size() == 0 || queue.size() == nums.length) {
      return -1;
    }

    int day = 0;

    int[][] offsets = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    while (queue.size() > 0 && total > 0) {
      LinkedList<int[]> newQueue = new LinkedList<>();

      for (int[] pos : queue) {
        int i = pos[0];
        int j = pos[1];

        for (int[] offset : offsets) {
          int newI = i + offset[0];
          int newJ = j + offset[1];

          if (newI >= 0 && newI < n && newJ >= 0 && newJ < n && matrix[newI][newJ] == 0) {
            matrix[newI][newJ] = 1;
            newQueue.add(new int[] {newI, newJ});
            total--;
          }
        }
      }

      queue = newQueue;
      day++;
    }

    return day;
  }
}

Python算法源码

import math

# 输入获取
nums = list(map(int, input().split(",")))


# 算法入口
def getResult():
    # 矩阵 n x n
    n = int(math.sqrt(len(nums)))

    # 未污染区域数量
    total = len(nums)

    # 矩阵
    matrix = [[0 for _ in range(n)] for _ in range(n)]

    # BFS队列
    queue = []

    for i in range(n):
        for j in range(n):
            matrix[i][j] = nums[i * n + j]
            if matrix[i][j] == 1:
                queue.append([i, j])
                total -= 1

    if len(queue) == 0 or len(queue) == len(nums):
        return -1

    # 上下左右偏移量
    offsets = ((-1, 0), (1, 0), (0, -1), (0, 1))

    # 扩散天数
    day = 0

    while len(queue) > 0 and total > 0:
        newQueue = []

        for i, j in queue:
            for offsetX, offsetY in offsets:
                newI = i + offsetX
                newJ = j + offsetY

                if 0 <= newI < n and 0 <= newJ < n and matrix[newI][newJ] == 0:
                    matrix[newI][newJ] = 1
                    newQueue.append([newI, newJ])
                    total -= 1

        queue = newQueue
        day += 1

    return day


# 算法调用
print(getResult())

C算法源码

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

#define MAX_SIZE 1024

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 matrix[MAX_SIZE][MAX_SIZE] = {0};
int nums[MAX_SIZE * MAX_SIZE];
int nums_size = 0;

int getResult();

int main() {
    while(scanf("%d", &nums[nums_size++])) {
        if(getchar() != ',') break;
    }

    printf("%dn", getResult());

    return 0;
}

int getResult() {
    // 矩阵 n x n
    int n = (int) sqrt(nums_size);

    // 未污染水域数量
    int total = nums_size;

    // BFS队列
    LinkedList* queue = new_LinkedList();

    for(int i=0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            matrix[i][j] = nums[i * n + j];

            if(matrix[i][j] == 1) {
                addLast_LinkedList(queue, i * n + j);
                total--;
            }
        }
    }

    if(queue->size == 0 || queue->size == nums_size) {
        return -1;
    }

    // 上下左右偏移量
    int offsets[4][2] = {{1,  0},
                         {-1, 0},
                         {0,  1},
                         {0,  -1}};

    // 扩散时间
    int day = 0;

    // 如果扩散点没有了，或者所有点已被扩散，则停止循环
    while (queue->size > 0 && total > 0) {
        LinkedList *newQueue = new_LinkedList();

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

            for (int i = 0; i < 4; i++) {
                int newX = x + offsets[i][0];
                int newY = y + offsets[i][1];

                if (newX >= 0 && newX < n && newY >= 0 && newY < n && matrix[newX][newY] == 0) {
                    // 将点被扩散的时间记录为该点的值
                    matrix[newX][newY] = 1;
                    // 被扩散到的点将变为新的扩散源
                    addLast_LinkedList(newQueue, newX * n + newY);
                    // 未被扩散点的数量--
                    total--;
                }
            }
            cur = cur->next;
        }

        queue = newQueue;
        day++;
    }

    return day;
}

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++;
}