题目描述

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

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

输入描述

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

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

输出描述

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

示例：

python算法源码

# 定义深度优先搜索函数
def dfs(i, j):
    # 如果坐标超出范围，或当前位置为0（代表不是服务器），或已经访问过，返回0
    if i < 0 or i >= n or j < 0 or j >= m or server[i][j] == 0 or visited[i][j]:
        return 0

    # 标记当前位置已访问
    visited[i][j] = True

    # 计数当前节点，并递归计算四个方向的服务器数量
    count = 1
    count += dfs(i - 1, j)  # 向上搜索
    count += dfs(i + 1, j)  # 向下搜索
    count += dfs(i, j - 1)  # 向左搜索
    count += dfs(i, j + 1)  # 向右搜索

    # 返回与当前节点相连的服务器总数
    return count

if __name__ == "__main__":
    # 读取行数n和列数m
    n, m = map(int, input().split())

    # 初始化服务器网格和访问状态网格
    server = []
    visited = []

    # 读取服务器网格数据
    for _ in range(n):
        server.append(list(map(int, input().split())))
        visited.append([False] * m)  # 初始化未访问状态

    # 初始化最大服务器数量为0
    ans = 0

    # 遍历网格每个位置，使用DFS搜索最大的服务器数量
    for i in range(n):
        for j in range(m):
            ans = max(ans, dfs(i, j))  # 更新最大服务器数量

    # 输出最大服务器数量
    print(ans)

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;

// 表示矩形的尺寸
typedef struct {
    int width; // 宽度
    int height; // 高度
} Dimensions;

// 创建并返回一个新的 Dimensions 对象
Dimensions *new_Dimensions(int width, int height) {
    Dimensions *dim = (Dimensions *)malloc(sizeof(Dimensions));
    dim->width = width;
    dim->height = height;
    return dim;
}

// 创建并返回一个新的空链表
LinkedList *new_LinkedList() {
    LinkedList *list = (LinkedList *)malloc(sizeof(LinkedList));
    list->size = 0;
    list->head = NULL;
    list->tail = NULL;
    return list;
}

// 在链表末尾添加一个元素
void addLast_LinkedList(LinkedList *list, int ele) {
    ListNode *node = (ListNode *)malloc(sizeof(ListNode));
    node->ele = ele;
    node->prev = NULL;
    node->next = NULL;

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

    list->size++;
}

// 从链表头部移除一个元素并返回其值
int removeFirst_LinkedList(LinkedList *list) {
    if (list->size == 0) exit(-1);

    ListNode *removed = list->head;

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

    list->size--;

    int res = removed->ele;

    free(removed);

    return res;
}

// 方向偏移数组
int offsets[4][2] = {{-1, 0},
                      {1, 0},
                      {0, -1},
                      {0, 1}};

// 获取 Dimensions 对象的宽度
int getWidth(Dimensions *dim) {
    return dim->width;
}

// 获取 Dimensions 对象的高度
int getHeight(Dimensions *dim) {
    return dim->height;
}

// 使用 BFS 算法计算联通区域的大小
int bfs(int i, int j, int **matrix, Dimensions *dim);

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    Dimensions *dim = new_Dimensions(m, n); // 创建 Dimensions 对象

    int **matrix = (int **)malloc(sizeof(int *) * getHeight(dim)); // 分配二维数组空间
    for (int i = 0; i < getHeight(dim); i++) {
        matrix[i] = (int *)malloc(sizeof(int) * getWidth(dim));
        for (int j = 0; j < getWidth(dim); j++) {
            scanf("%d", &matrix[i][j]);
        }
    }

    int res = 0;

    int i = 0;
    while (i < getHeight(dim)) { // 遍历矩阵的每一行
        int j = 0;
        while (j < getWidth(dim)) { // 遍历矩阵的每一列
            if (matrix[i][j] == 1) {
                res = (int)fmax(res, bfs(i, j, matrix, dim)); // 计算联通区域的大小并更新结果
            }
            j++;
        }
        i++;
    }

    printf("%d\n", res);
}

// 使用 BFS 算法计算联通区域的大小
int bfs(int i, int j, int **matrix, Dimensions *dim) {
    LinkedList *queue = new_LinkedList(); // 创建一个空队列用于 BFS
    int count = 1; // 联通区域的大小，初始为1
    matrix[i][j] = 0; // 将当前位置标记为已访问

    addLast_LinkedList(queue, i * getWidth(dim) + j); // 将当前位置加入队列

    while (queue->size > 0) { // 当队列不为空时
        int pos = removeFirst_LinkedList(queue); // 取出队首位置

        int x = pos / getWidth(dim); // 计算行号
        int y = pos % getWidth(dim); // 计算列号

        for (int k = 0; k < 4; k++) { // 遍历四个方向
            int newX = x + offsets[k][0]; // 计算新的行号
            int newY = y + offsets[k][1]; // 计算新的列号

            if (newX >= 0 && newX < getHeight(dim) && newY >= 0 && newY < getWidth(dim) && matrix[newX][newY] == 1) {
                count++; // 联通区域大小加1
                matrix[newX][newY] = 0; // 将新位置标记为已访问
                addLast_LinkedList(queue, newX * getWidth(dim) + newY); // 将新位置加入队列
            }
        }
    }

    return count; // 返回联通区域的大小
}

Java算法源码

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

public class Main {
    static final int MAX_SIZE = 100;
    static int[][] offsets = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    static int n, m;
    static int[][] matrix = new int[MAX_SIZE][MAX_SIZE];

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt(); // 读取矩阵的行数
        m = scanner.nextInt(); // 读取矩阵的列数

        // 读取矩阵数据
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                matrix[i][j] = scanner.nextInt();
            }
        }

        int res = 0;

        // 遍历整个矩阵，找到每个岛屿的最大面积
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == 1) {
                    res = Math.max(res, bfs(i, j)); // 计算最大面积
                }
            }
        }

        System.out.println(res); // 输出结果
    }

    public static int bfs(int i, int j) {
        Queue<Integer> queue = new LinkedList<>(); // 创建一个队列用于广度优先搜索

        int count = 1; // 计数器，记录岛屿的面积
        matrix[i][j] = 0; // 将当前位置标记为已访问

        queue.add(i * m + j); // 将当前位置加入队列

        while (!queue.isEmpty()) {
            int pos = queue.remove(); // 从队列中取出一个位置

            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; // 将相邻位置标记为已访问
                    queue.add(newX * m + newY); // 将相邻位置加入队列
                }
            }
        }

        return count; // 返回岛屿的面积
    }
}