P3503. 网格相邻消除

解题思路

注意，本题和 岛屿数量 几乎完全一致。唯一的区别在于，本题需要考虑 八个方向 而不是四个方向。

考虑八个方向时，我们需要定义方向数组为：

剩余过程就是常规的 DFS / BFS 过程。

BFS

1. 初始化 Checklist 2. 双重循环 遍历所有点作为 BFS 的起点：

• 找到一个 没遍历过 且 值为 1 的点：
• （开始 BFS）
• 初始化队列（包含起点）
• Checklist 修改（起点）
• while（队列不为空）：
• 弹出队头元素 (x, y)
• for 循环 考虑 (x, y) 的近邻点（8 个方向）：
• 越界判断 + 找到一个 没遍历过 且 值为 1 的近邻点 (nx, ny)：
• 队列更新 (nx, ny)
• Checklist 修改 (nx, ny)
• 更新连通块数量

DFS

1. 定义 DFS 函数，包含参数 (x, y)：

• Checklist 修改 (x, y)
• for 循环 考虑 (x, y) 的近邻点（8 个方向）：
• 越界判断 + 找到一个 没遍历过 且 值为 1 的近邻点 (nx, ny)：
• 递归调用 DFS 函数，传入 (nx, ny)

2. 初始化 Checklist 3. 双重循环 遍历所有点作为 DFS 的起点：

• 找到一个 没遍历过 且 值为 1 的点：
• （开始 DFS）
• DFS 函数入口
• 更新连通块数量

代码

解法一：BFS

复杂度分析 设网格为 N 行 M 列。本题的答案等于值为 1 的八连通块的个数，每个连通块只需要点击一次。

• 时间：外层双重循环枚举所有格子是 O(N·M)；BFS 中每个格子在入队时就被 checkList 标记，因此一生最多入队、出队一次，出队时检查 8 个方向的邻格也是常数次操作，所有 BFS 累计 O(N·M)。总时间复杂度为 O(N·M)。
• 空间：grid 和 checkList 各占 O(N·M)，队列在最坏情况下同量级，空间复杂度为 O(N·M)。

与四方向的「岛屿数量」相比，方向数从 4 变成 8 只是常数因子变大，复杂度量级完全不变。