🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解

💻 ACM银牌🥈| 多次AK大厂笔试 ｜ 编程一对一辅导

👏 感谢大家的订阅➕ 和 喜欢💗

📎在线评测链接

https://app5938.acapp.acwing.com.cn/contest/2/problem/OD1074

🌍 评测功能需要 ⇒ 订阅专栏 ⇐ 后私信联系清隆解锁～

🍓OJ题目截图

☕️ 局域网中的服务器个数

题目描述

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

输入格式

第一行输入两个正整数 $n$ 和 $m$，$1\le n,m\le 100$。
接下来为 $n\ast m$ 的二维数组，代表服务器信息。

输出格式

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

样例输入

2 2
1 0
1 1

样例输出

3

样例解释

矩阵的第 0 列和第 1 行包含了三台服务器，它们相互连接，可以组成局域网。

数据范围

• $1\le n,m\le 100$
• 矩阵中的值为 0 或 1

题解

题目要求找到最大的局域网，并输出其中包含的服务器个数。我们可以使用深度优先搜索（DFS）来遍历矩阵，寻找所有连接的服务器。

具体步骤如下：

1. 初始化：定义一个二维数组 vis 来标记访问状态，定义变量 ans 来存储最大局域网的服务器个数。
2. 定义方向数组：用 sx 和 sy 来表示上下左右四个方向。
3. 深度优先搜索（DFS）：编写 dfs 函数，通过递归遍历所有相邻的服务器，并记录服务器个数。
4. 遍历矩阵：对矩阵的每个元素进行遍历，如果当前元素是服务器且未访问过，调用 dfs 函数计算当前局域网的服务器个数，并更新最大局域网的服务器个数。

通过上述步骤，可以找到最大的局域网并输出其包含的服务器个数。

参考代码

• Python

n, m = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(n)]
visited = [[0] * m for _ in range(n)]
max_servers = 0
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def dfs(x, y):
    count = 1
    stack = [(x, y)]
    while stack:
        cx, cy = stack.pop()
        for i in range(4):
            nx, ny = cx + dx[i], cy + dy[i]
            if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny] and matrix[nx][ny] == 1:
                visited[nx][ny] = 1
                count += 1
                stack.append((nx, ny))
    return count

for i in range(n):
    for j in range(m):
        if matrix[i][j] == 1 and not visited[i][j]:
            visited[i][j] = 1
            max_servers = max(max_servers, dfs(i, j))

print(max_servers)

• Java

import java.util.*;

public class Main {
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static int n, m;
    static int[][] matrix;
    static boolean[][] visited;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        matrix = new int[n][m];
        visited = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                matrix[i][j] = sc.nextInt();
            }
        }

        int maxServers = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == 1 && !visited[i][j]) {
                    maxServers = Math.max(maxServers, dfs(i, j));
                }
            }
        }

        System.out.println(maxServers);
    }

    static int dfs(int x, int y) {
        int count = 1;
        Stack<int[]> stack = new Stack<>();
        stack.push(new int[]{x, y});
        visited[x][y] = true;

        while (!stack.isEmpty()) {
            int[] current = stack.pop();
            int cx = current[0];
            int cy = current[1];
            for (int i = 0; i < 4; i++) {
                int nx = cx + dx[i];
                int ny = cy + dy[i];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] && matrix[nx][ny] == 1) {
                    stack.push(new int[]{nx, ny});
                    visited[nx][ny] = true;
                    count++;
                }
            }
        }
        return count;
    }
}

• Cpp

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int n, m;
vector<vector<int>> matrix;
vector<vector<bool>> visited;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

int dfs(int x, int y) {
    int count = 1;
    stack<pair<int, int>> s;
    s.push({x, y});
    visited[x][y] = true;
    
    while (!s.empty()) {
        int cx = s.top().first;
        int cy = s.top().second;
        s.pop();
        
        for (int i = 0; i < 4; ++i) {
            int nx = cx + dx[i];
            int ny = cy + dy[i];
            
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] && matrix[nx][ny] == 1) {
                s.push({nx, ny});
                visited[nx][ny] = true;
                count++;
            }
        }
    }
    return count;
}

int main() {
    cin >> n >> m;
    matrix.resize(n, vector<int>(m));
    visited.resize(n, vector<bool>(m, false));
    
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> matrix[i][j];
        }
    }
    
    int maxServers = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (matrix[i][j] == 1 && !visited[i][j]) {
                maxServers = max(maxServers, dfs(i, j));
            }
        }
    }
    
    cout << maxServers << endl;
    return 0;
}