【大厂机试题解法笔记】可以组成网络的服务器

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

输入描述
第一行输入两个正整数，n 和 m，0 < n, m <= 100
之后为 n * m 的二维数组，代表服务器信息

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

用例

输入：

2 2
1 0
1 1

输出：   

3

说明：

[0][0]、[1][0]、[1][1]三台服务器相互连接，可以组成局域网

思考

矩阵中相邻的1构成局域网，统计所有局域网中最大的。遍历矩阵，判断如果是 1 就 DFS 搜索周围的1，搜索过程中的统计 1 的数目，直到没有1或遇到矩阵边界时结束一轮 DFS，将本轮统计的局域网大小（1的数量）更新结果变量，取最大值。完成所有遍历和搜索，得到最大局域网数量。

算法过程

1. 输入处理：

   • 读取矩阵的行数 n 和列数 m
   • 逐行读取矩阵数据，存储为二维数组 mtx

2. 初始化辅助结构：

   • 创建与矩阵大小相同的 visited 数组，用于标记已访问的服务器
   • 初始化 maxCount 记录最大局域网服务器数量

3. 深度优先搜索（DFS）：

   • 终止条件：超出矩阵边界、当前位置无服务器或已访问
   • 标记当前服务器：将当前位置标记为已访问
   • 递归探索：向上下左右四个方向递归搜索相连的服务器
   • 返回值：当前局域网的服务器总数

4. 遍历矩阵：

   • 对每个位置 (i, j)：
     • 若存在未访问的服务器（mtx[i][j] == 1 且未被访问）
     • 启动 DFS 计算当前局域网大小
     • 更新最大局域网大小 maxCount

5. 遍历结束后，maxCount 即为最大局域网的服务器数量。时间复杂度为 O (n*m)。

参考代码

function solution() {const [n, m] = readline().split(' ').map(Number);const mtx = Array(n);for (let i = 0; i < n; i++) {mtx[i] = readline().split(" ").map(Number);}const visited = Array.from({length: n}, () => new Array(m).fill(false));let maxCount = 0;const dfs = function(x, y) {if (x < 0 || x >= n || y < 0 || y >= m || mtx[x][y] !==1 || visited[x][y]) {return 0;}visited[x][y] = true;let count = 1;count += dfs(x-1, y);count += dfs(x+1, y);count += dfs(x, y-1);count += dfs(x, y+1);return count;};for (let i = 0; i < n; i++) {for (let j = 0; j < m; j++) {if (mtx[i][j] === 1 && !visited[i][j]) {const count = dfs(i, j);maxCount = Math.max(maxCount, count);}}}console.log(maxCount);
}const cases = [`2 2
1 0
1 1`
];let caseIndex = 0;
let lineIndex = 0;const readline = (function () {let lines = [];return function () {if (lineIndex === 0) {lines = cases[caseIndex].trim().split("\n").map((line) => line.trim());}return lines[lineIndex++];};
})();cases.forEach((_, i) => {caseIndex = i;lineIndex = 0;solution();
});