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

在一个机房中，服务器的位置标识在 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();
});