【机试刷题】华为OD-可以组成网络的服务器

合集 – 牛客华为面试题(12)
1.【C 语言基础】牛客华为机试必知必会的C库函数2023-12-012.【C语言基础】float、double 浮点数类型的四舍五入问题2023-12-043.【Cpp 语言基础】泛型算法 stable_sort() 在二元组pair上的应用2023-12-094.【Linux 基础】正则表达式 与 通配符 区别2023-12-035.【动态规划】leetcode 不同路径问题2023-12-276.【动态规划】经典0-1背包问题2023-12-197.【机试刷题】顺时针旋转矩阵01-098.【机试刷题】回溯法求解n个元素的集合的幂集01-05
9.【机试刷题】华为OD-可以组成网络的服务器01-0110.【机试刷题】牛客OJ在线编程常见输入输出练习2023-12-2711.【机试刷题】HJ31 单词倒排 解法2023-12-2212.【机考刷题】爱吃香蕉的珂珂2023-12-25

收起

题目描述

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

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

输入描述

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

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

输出描述

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

用例

参考

#include <iostream>
using namespace std;

int n, m;//n表示行数，m表示列数
int server[100][100]; // 定义一个矩阵，用于存储服务器的状态

// 定义一个深度优先搜索函数，用于搜索当前位置的连通块大小
int dfs(int i, int j, int count) {
    //如果当前位置没有服务器， 或者当前位置超出矩阵边界，则返回当前连通块大小
    if (i < 0 || i >= n || j < 0 || j >= m || server[i][j] == 0) 
    {
        return count;
    }

    // 如果当前位置有服务器，则将其状态改为0，表示已经搜索过
    count++;
    server[i][j] = 0;//标记已经搜索过，防止以后重复搜。

    // 分别向上、下、左、右四个方向递归搜索，并累加连通块大小
    count = dfs(i - 1, j, count); // 上
    count = dfs(i + 1, j, count); // 下
    count = dfs(i, j - 1, count); // 左
    count = dfs(i, j + 1, count); // 右

    return count;
}

int main() {
    // 读入矩阵的行数和列数
    cin >> n >> m;

    // 读入矩阵中每个位置的状态（0表示没有服务器，1表示有服务器）
    for (int i = 0; i < n; i  ) {
        for (int j = 0; j < m; j  ) {
            cin >> server[i][j];
        }
    }

    int ans = 0; // 定义一个变量，用于存储最大连通块大小

    // 枚举矩阵中的每个位置，以该位置为起点进行深度优先搜索，并更新最大连通块大小
    for (int i = 0; i < n; i  ) {
        for (int j = 0; j < m; j  ) {
            ans = max(ans, dfs(i, j, 0));
        }
    }

    // 输出最大连通块大小
    cout << ans << endl;

    return 0;
}

本文转载自： https://www.swvq.com/boutique/detail/tangikkgf