(B卷,200分)- 返回矩阵中非1的元素个数（Java & JS & Python & C）

题目描述

存在一个m*n的二维数组，其成员取值范围为0，1，2。

其中值为1的元素具备同化特性，每经过1S，将上下左右值为0的元素同化为1。

而值为2的元素，免疫同化。

将数组所有成员随机初始化为0或2，再将矩阵的[0, 0]元素修改成1，在经过足够长的时间后求矩阵中有多少个元素是0或2（即0和2数量之和）。

输入描述

输入的前两个数字是矩阵大小。后面是数字矩阵内容。

输出描述

返回矩阵中非1的元素个数。

用例

题目解析

本题可以使用广度优先搜索BFS解决。

关于广度优先搜索，可以看：

JS算法源码

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

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

const lines = [];
let m, n;
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length == 1) {
    [m, n] = lines[0].split(" ").map(Number);
  }

  if (m && lines.length == m + 1) {
    lines.shift();

    const matrix = lines.map((s) => s.split(" ").map(Number));
    matrix[0][0] = 1;

    console.log(getResult(m, n, matrix));
  }
});

function getResult(m, n, matrix) {
  // 上、下、左、右偏移量
  const offsets = [
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1],
  ];

  // 广搜队列, 初始时只有矩阵[0,0]位置元素为1
  const queue = [[0, 0]];

  // count记录矩阵中值为1的元素的个数
  let count = 1;

  // 广搜
  while (queue.length > 0) {
    const [x, y] = queue.shift();

    for (let offset of offsets) {
      const newX = x + offset[0];
      const newY = y + offset[1];

      if (
        newX >= 0 &&
        newX < m &&
        newY >= 0 &&
        newY < n &&
        matrix[newX][newY] == 0
      ) {
        matrix[newX][newY] = 1;
        count++;
        queue.push([newX, newY]);
      }
    }
  }

  return m * n - count;
}

Java算法源码

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

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

    int m = sc.nextInt();
    int n = sc.nextInt();

    int[][] matrix = new int[m][n];
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        matrix[i][j] = sc.nextInt();
      }
    }

    matrix[0][0] = 1;

    System.out.println(getResult(m, n, matrix));
  }

  public static int getResult(int m, int n, int[][] matrix) {
    // 上、下、左、右偏移量
    int[][] offsets = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    // 广搜队列
    LinkedList<int[]> queue = new LinkedList<>();

    // 初始时只有矩阵[0,0]位置元素为1
    queue.add(new int[] {0, 0});

    // count记录矩阵中值为1的元素的个数
    int count = 1;

    // 广搜
    while (queue.size() > 0) {
      int[] pos = queue.removeFirst();

      int x = pos[0];
      int y = pos[1];

      for (int[] offset : offsets) {
        int newX = x + offset[0];
        int newY = y + offset[1];

        if (newX >= 0 && newX < m && newY >= 0 && newY < n && matrix[newX][newY] == 0) {
          matrix[newX][newY] = 1;
          count++;
          queue.add(new int[] {newX, newY});
        }
      }
    }

    return m * n - count;
  }
}

Python算法源码

# 输入获取
m, n = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(m)]
matrix[0][0] = 1


# 算法入口
def getResult():
    # 上、下、左、右偏移量
    offsets = ((-1, 0), (1, 0), (0, -1), (0, 1))

    # 广搜队列, 初始时只有矩阵[0,0]位置元素为1
    queue = [[0, 0]]

    # count记录矩阵中值为1的元素的个数
    count = 1

    # 广搜
    while len(queue) > 0:
        x, y = queue.pop(0)

        for offset in offsets:
            newX = x + offset[0]
            newY = y + offset[1]

            if m > newX >= 0 and n > newY >= 0 and matrix[newX][newY] == 0:
                matrix[newX][newY] = 1
                count += 1
                queue.append([newX, newY])

    return m * n - count


# 算法调用
print(getResult())

C算法源码

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

/**
 * 下面时基于单向链表实现的队列，入队enqueue，出队dequeue
 */
typedef int bool;
#define TRUE 1
#define FALSE 0

// 队列元素类型（初始默认为int，后期可以改为需要的类型）
typedef int E;

// 单向链表节点结构体
typedef struct ListNode {
    E ele; // 节点值
    struct ListNode *next; // 后继节点
} Node;

// 链表结构体
typedef struct LinkedList {
    Node *head; // 头节点
    Node *tail; // 尾节点
    int size; // 队列长度
} Queue; // 使用链表模拟队列

/*!
 * 初始化队列
 * @return 队列指针
 */
Queue *init() {
    // 申请内存
    Queue *queue = (Queue *) malloc(sizeof(Queue));

    // 申请内存失败
    if (queue == NULL) {
        return NULL;
    }

    // 初始化队列成员
    queue->head = NULL;
    queue->tail = NULL;
    queue->size = 0;

    return queue;
}

/*!
 * 释放队列
 * @param queue 队列
 */
void destroy(Queue* queue) {
    Node* cur = queue->head;

    // 释放队列各个节点的内存
    while(cur != NULL) {
        Node* tmp = cur->next;
        free(cur);
        cur = tmp;
    }

    // 释放队列结构体内存
    free(queue);
}

/*!
 * 入队
 * @param queue 队列
 * @param ele 入队元素
 * @return 操作结果
 */
bool enqueue(Queue* queue, E ele) {
    // 申请内存，创建一个新节点
    Node *node = (Node *) malloc(sizeof(Node));

    // 申请内存失败
    if (node == NULL) {
        return FALSE;
    }

    // 初始化节点
    node->ele = ele;
    node->next = NULL;

    if (queue->size == 0) {
        // 空队列插入
        queue->head = node;
        queue->tail = node;
    } else {
        // 尾插
        queue->tail->next = node;
        queue->tail = node;
    }

    // 节点数+1
    queue->size++;

    return TRUE;
}

/*!
 * 出队
 * @param queue 队列
 * @return 出队元素的地址（注意：返回值特地申请了一块内存来存储，因此使用完后，需要释放返回值占用的内存）
 */
E* dequeue(Queue* queue) {
    // 空队列无法出队
    if(queue->size == 0) {
        return NULL;
    }

    // 指向将被删除节点
    Node *removeNode;

    if (queue->size == 1) {
        // 单节点队列删除唯一节点
        removeNode = queue->head;
        queue->head = NULL;
        queue->tail = NULL;
    } else {
        // 头删
        removeNode = queue->head;
        queue->head = queue->head->next;
    }

    // 队列节点个数-1
    queue->size--;

    // 申请一块内存用于存放被删除节点的值
    E *p = (E *) malloc(sizeof(E));
    *p = removeNode->ele;

    // 释放被删除节点的空间
    free(removeNode);

    return p;
}


/**
 * 算法代码逻辑
 */

#define MAX_ROWS 100
#define MAX_COLS 100

int m, n;
int matrix[MAX_ROWS][MAX_COLS];

int getResult();

int main() {
    scanf("%d %d", &m, &n);

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &matrix[i][j]);
        }
    }

    matrix[0][0] = 1;

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

    return 0;
}

int getResult() {
    int offsets[4][2] = {{-1, 0},
                         {1,  0},
                         {0,  1},
                         {0,  -1}};

    Queue *queue = init();

    enqueue(queue, 0 * n + 0);
    int count = 1;

    while (queue->size > 0) {
        int* pos = dequeue(queue);

        int x = *pos / n;
        int y = *pos % n;

        // dequeue返回值是存放在一块专门申请的内存中的，因此需要释放
        free(pos);

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

            if (newX >= 0 && newX < m && newY >= 0 && newY < n && matrix[newX][newY] == 0) {
                matrix[newX][newY] = 1;
                count++;
                enqueue(queue, newX * n + newY);
            }
        }
    }

    // 释放链表内存
    destroy(queue);

    return m * n - count;
}