P3498. 可以组成网络的服务器

解题思路

注意，本题和 经典题型（岛屿的最大面积）完全一致，直接套用模板即可。

解法一：DFS

使用 深度优先搜索（DFS） 遍历网格中的每个格子。当遇到值为 1 的格子时，说明发现了一个岛屿，此时从该格子出发，递归地访问所有相邻的 1，并统计该岛屿的面积。

核心步骤：

1. 遍历整个网格，对每个格子调用 DFS。 2. 在 DFS 中，如果当前格子越界或值为 0，则返回 0。 3. 否则，将当前格子标记为 0（避免重复访问），并递归访问其上下左右四个相邻格子。 4. 返回当前格子面积 1 加上四个方向递归返回的面积之和。 5. 在遍历过程中，记录并更新最大岛屿面积。

关键代码片段如下：

注意：标记已访问的格子为 0 是避免重复计算的关键，否则会导致无限递归。

思路展开 参考代码用 DFS 求网格中最大连通块的大小，和「岛屿的最大面积」是同一个模板。主函数用双重循环扫描整个 n × m 网格，checkList 数组记录每个格子是否已被访问。当遇到一个值为 1 且未访问的格子时，说明发现了一个新的局域网：先把计数器 area 清零，再从这个格子进入 DFS。DFS 每进入一个格子，就立刻在 checkList 上做标记并把 area 加一，然后沿 DIRECTIONS 定义的上、下、左、右四个方向尝试递归，只有当邻格在边界内、未被访问且值为 1 时才继续深入。这样一轮 DFS 恰好走遍当前连通块里的每一台服务器，结束时 area 就是这个局域网包含的服务器数。每处理完一个连通块，用 ans = Math.max(ans, area) 更新答案，最终输出的 ans 即最大局域网的规模。这份实现与正文示例中「把访问过的格子改成 0」的写法等价，只是改用独立的 checkList 做标记，不破坏原始网格数据。

复杂度分析 设网格为 n 行 m 列。

• 时间：双重循环枚举每个格子是 O(n·m)；由于 checkList 的存在，每个格子一生只会被 DFS 真正进入一次，每次只检查 4 个方向，所有 DFS 加起来也是 O(n·m)。总时间复杂度为 O(n·m)。
• 空间：grid 和 checkList 各占 O(n·m)；DFS 递归栈在最坏情况（所有服务器连成一个大连通块）下深度可达 O(n·m)。