(C卷,200分)- 可以组成网络的服务器（Java & JS & Python & C）

题目描述

在一个机房中，服务器的位置标识在 n*m 的整数矩阵网格中，1 表示单元格上有服务器，0 表示没有。如果两台服务器位于同一行或者同一列中紧邻的位置，则认为它们之间可以组成一个局域网。

请你统计机房中最大的局域网包含的服务器个数。

输入描述

第一行输入两个正整数，n和m，0<n,m<=100

之后为n*m的二维数组，代表服务器信息

输出描述

最大局域网包含的服务器个数。

用例

题目解析

本题可以用深度优先搜索DFS求解。

我们找到一个服务器后，就再去其上下左右找下一个服务器，当找到新服务器，再递归去找其上下左右，按此逻辑，就像拔地瓜藤一样，一下子把所有地瓜都拔出来。而这就是深度优先搜索，即dfs。

为了避免重复统计，我们将统计过的服务器位置的值从1变为0。

2023.06.18

本题极限用例下，深度优先搜索（递归实现）可能会发生Stack Overflow，因此推荐使用广度优先搜索，广度优先搜索依赖于自定义的队列，来完成图的遍历，因此不会发生Stack Overflow。

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

当然，本题也可以基于深度优先搜索（自定义栈）实现，对应代码可以参考：

华为OD机试 – 寻找最大价值的矿堆（Java & JS & Python）_伏城之外的博客-CSDN博客

JavaScript算法源码

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

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

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

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

  if (n && lines.length === n + 1) {
    lines.shift();
    matrix = lines.map((line) => line.split(" ").map(Number));

    console.log(getResult());

    lines.length = 0;
  }
});

function getResult() {
  let ans = 0;
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (matrix[i][j] == 1) ans = Math.max(ans, bfs(i, j));
    }
  }

  return ans;
}

const offsets = [
  [-1, 0],
  [1, 0],
  [0, -1],
  [0, 1],
];

function bfs(i, j) {
  let count = 1;
  matrix[i][j] = 0;

  const queue = [[i, j]];

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

    for (let [offsetX, offsetY] of offsets) {
      const newX = x + offsetX;
      const newY = y + offsetY;

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

  return count;
}

Java算法源码

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

public class Main {
  static int n;
  static int m;
  static int[][] matrix;

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

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

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

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

  public static int getResult() {
    int ans = 0;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        if (matrix[i][j] == 1) ans = Math.max(ans, bfs(i, j));
      }
    }

    return ans;
  }

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

  public static int bfs(int i, int j) {
    LinkedList<int[]> queue = new LinkedList<>();

    int count = 1;
    matrix[i][j] = 0;

    queue.add(new int[] {i, j});

    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 < n && newY >= 0 && newY < m && matrix[newX][newY] == 1) {
          count++;
          matrix[newX][newY] = 0;
          queue.add(new int[] {newX, newY});
        }
      }
    }

    return count;
  }
}

Python算法源码

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

offsets = ((-1, 0), (1, 0), (0, -1), (0, 1))


def bfs(i, j):
    count = 1
    matrix[i][j] = 0

    queue = [[i, j]]

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

        for offsetX, offsetY in offsets:
            newX = x + offsetX
            newY = y + offsetY

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

    return count


# 算法入口
def getResult():
    ans = 0

    for i in range(n):
        for j in range(m):
            if matrix[i][j] == 1:
                ans = max(ans, bfs(i, j))

    return ans


# 算法调用
print(getResult())

C算法源码

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

#define MAX_SIZE 100

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

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

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->prev = NULL;
    node->next = NULL;

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

    link->size++;
}

int removeFirst_LinkedList(LinkedList *link) {
    if (link->size == 0) exit(-1);

    ListNode *removed = link->head;

    if (link->size == 1) {
        link->head = NULL;
        link->tail = NULL;
    } else {
        link->head = link->head->next;
        link->head->prev = NULL;
    }

    link->size--;

    int res = removed->ele;

    free(removed);

    return res;
}

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

int n, m;
int matrix[MAX_SIZE][MAX_SIZE];

int bfs(int i, int j);

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

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

    int res = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (matrix[i][j] == 1) {
                res = (int) fmax(res, bfs(i, j));
            }
        }
    }

    printf("%dn", res);
}

int bfs(int i, int j) {
    LinkedList *queue = new_LinkedList();

    int count = 1;
    matrix[i][j] = 0;

    addLast_LinkedList(queue, i * m + j);

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

        int x = pos / m;
        int y = pos % m;

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

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

    return count;
}