艾尔罗大迷宫（统计不可到达格子）

虾皮（Shopee）2026 春招笔试编程题 · 核心代码模式

题目描述

设计一个迷宫游戏系列"艾尔罗"。在设计初期为了方便，使用 N×N 矩阵表示迷宫：

• 0 表示可到达区域（可以通行的格子）；
• 1 表示原生不可到达区域（本身就是障碍，无法进入）。

玩家从左上角 [0,0] 出发，只能沿着上、下、左、右四个方向移动。需要统计整张地图里无法从起点到达的格子总数。这里的"无法到达"包含两类：

• 原本就是障碍的格子（值为 1）；
• 虽然值为 0，但因为被障碍隔开、无法从起点走到的格子。

约束：

• 迷宫一定是 N×N 二维数组；
• 起点 [0,0] 一定可达，值为 0；
• 迷宫元素只会是 0 或 1；
• 数据范围：1 ≤ N ≤ 200。

输入格式

• 第一行：整数 N，表示迷宫边长；
• 接下来 N 行：每行 N 个整数（0 或 1），表示迷宫地图。

输出格式

• 一个整数，表示不可到达的格子总数。

示例

示例 1

输入：

4
0 1 1 0
1 0 0 0
0 1 0 1
0 1 1 0

输出：

15

说明： 起点 [0,0] 的上、下、右都是障碍（或边界），整张地图只有起点自己可达，所以答案是 16 - 1 = 15。

示例 2

输入：

4
0 0 0 0
1 0 0 1
0 0 1 0
0 0 0 1

输出：

5

说明： 除了 4 个障碍（1）之外，右下角 (2,3) 那块 0 也被障碍四面围住、无法从起点走到，所以总共有 4 + 1 = 5 个格子不可达。

示例 3

输入：

4
0 0 0 0
0 0 1 0
0 0 1 0
1 0 0 0

输出：

3

说明： 三个障碍 (1,2)、(2,2)、(3,0) 都是不可达的，其余所有 0 都能从起点走到，答案是 3。

---

解题思路

第一步：理解问题本质

题目要统计两类格子：障碍和被隔断的空地。如果分别去数，既麻烦又容易漏。

关键洞察：不可到达的格子数 = 总格子数 − 从起点能够走到的格子数。

因为：

• 所有能被 BFS/DFS 从起点访问到的格子，一定是可达空地；
• 没被访问到的格子，要么本身是障碍 1，要么虽然为 0 但不与起点连通；
• 这两类恰好就是题目要求统计的全部不可达格子。

所以只需要"从起点数出可达格子数"，剩下的全都是答案。

第二步：暴力解法

思路： 对每个格子都做一次搜索，判断它能否回到起点。

• 从任意一个格子出发 DFS/BFS，看它是否能到达 (0,0)；
• 能到达则可达，否则不可达，统计不可达个数。

def apply(self, generated_map):
    n = len(generated_map)
    count = 0
    for i in range(n):
        for j in range(n):
            # 每个格子做一次 BFS，判断能否到达 (0,0)
            if not self._can_reach(generated_map, i, j):
                count += 1
    return count

为什么不够好：

• 每个格子都要做一次全图搜索，总复杂度是 O(N⁴)（N×N 个起点，每次搜索最坏 O(N²)）；
• N 最大到 200 时完全不可行；
• 大量搜索是重复的——同一个连通块里的格子被反复检查。

第三步：最优解法（从起点正向 BFS 一次）

思路： 反其道而行——不检查"每个格子能不能到达起点"，而是从起点出发一次 BFS，把能走到的地方全部标记出来，数个数。

1. 从 (0,0) 出发，用队列做 BFS；
2. 只有值为 0、在边界内、且没访问过的格子才能入队；
3. BFS 结束后，reachable 记录的就是所有可达空地的数量；
4. 答案 = N*N - reachable。

为什么 BFS 而不是 DFS？都可以，但 BFS 用显式队列实现，没有递归栈溢出的风险，对 N=200 的规模更稳妥。DFS 用迭代栈也可以。

正确性：

• BFS 会完整找出与起点属于同一个连通块的所有空地；
• 没有被访问到的格子只可能是障碍或被隔断的空地，正是要统计的对象；
• 因此 N*N - reachable 精确等于题目要求的不可达格子数。

---

完整代码实现

算法可视化 · 逐帧回放这道题的代码30 帧 · 录制输入 [[0, 1, 1, 0], [1, 0, 0, 0], [0, 1, 0, 1], [0, 1, 1, 0]]

from collections import deque
from typing import List

class Solution:
    def apply(self, generated_map: List[List[int]]) -> int:
        n = len(generated_map)

        # 记录每个格子是否访问过
        visited = [[False] * n for _ in range(n)]

        # 四个方向：上、下、左、右
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        # BFS 队列，从起点 (0,0) 出发
        q = deque()
        q.append((0, 0))
        visited[0][0] = True

        # 统计从起点能够到达的空地数（起点本身算一个）
        reachable = 0

        while q:
            x, y = q.popleft()
            reachable += 1

            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                # 新位置必须满足：边界内、值为 0、且没有访问过
                if 0 <= nx < n and 0 <= ny < n and generated_map[nx][ny] == 0 and not visited[nx][ny]:
                    visited[nx][ny] = True
                    q.append((nx, ny))

        # 总格子数 - 可达格子数 = 不可达格子数
        return n * n - reachable

笔试环境为"核心代码模式"，只需实现类方法；本地测试时在 if __name__ == "__main__": 中补充测试用例即可（见 code-training/shoppee/shoppee_maze_unreachable_count.py）。

---

示例推演

以示例 3为例，逐步追踪 BFS：

初始地图：
0 0 0 0
0 0 1 0
0 0 1 0
1 0 0 0

起点：(0,0)

第 1 层：

出队格子	新入队的 0 邻居
(0,0)	(0,1)、(1,0)

可达数 = 3（含起点）

第 2 层：

出队格子	新入队的 0 邻居
(0,1)	(0,2)
(1,0)	(2,0)

可达数 = 6

第 3 层：

出队格子	新入队的 0 邻居
(0,2)	(0,3)
(2,0)	(2,1)

可达数 = 9（(1,2) 是障碍，不入队）

第 4 层：

出队格子	新入队的 0 邻居
(0,3)	(1,3)
(2,1)	(3,1)

可达数 = 12

第 5 层：

出队格子	新入队的 0 邻居
(1,3)	(2,3)
(3,1)	(3,2)

可达数 = 15

第 6 层：

出队格子	新入队的 0 邻居
(2,3)	(3,3)

可达数 = 16

第 7 层： (3,3) 出队后没有新的 0 邻居，队列为空，BFS 结束。

最终可达数 reachable = 13，答案 = 4*4 - 13 = 3。

检查一下：障碍 (1,2)、(2,2)、(3,0) 正是那 3 个不可达格子，正确。

---

复杂度分析

解法	时间复杂度	空间复杂度	说明
暴力（每个格子反向搜索）	O(N⁴)	O(N²)	每个格子一次全图搜索，N=200 时不可行
最优（起点正向 BFS）	O(N²)	O(N²)	每个格子最多进队一次，visited 数组 + 队列

其中 N 为迷宫边长。

---

易错点总结

1. 用"单次行扫描"代替真正的遍历

错误： 只从左到右、从上到下扫一遍，把"左/上邻居可达"的格子标记为可达。

问题： 这种方法只能传播"向右、向下"的信息，无法处理需要先绕远路、再折回的连通形状。例如：

0 1 0
0 1 0
0 0 0

(0,2)、(1,2) 明明可以通过 (0,2) → (1,2) → (2,2) → (2,1) → (2,0) → (1,0) → (0,0) 的绕行路线与起点连通，但单向扫描时它们被访问到时，右侧、下方的邻居都还没被标记，导致被漏算为"不可达"。

正确做法： 用队列/栈做真正的 BFS/DFS，让信息可以向任意方向扩散。

2. 把起点也算漏

reachable 的初始值要包含起点本身。BFS 出队时计数，起点一开始就在队列里，所以不会漏。

3. 忘记障碍判定

只有值为 0 的格子才能入队。如果忘记判断 generated_map[nx][ny] == 0，障碍也会被算成"可达"，答案会偏小。

4. 越界检查顺序

必须先判断 0 <= nx < n and 0 <= ny < n，再访问 generated_map[nx][ny]，顺序反过来会越界报错。

---

扩展思考

• 只数被围住的空地（不含障碍）： 答案改为 N*N - reachable - count(障碍数)，即先统计障碍总数再减掉。
• 如果起点不保证为 0： 需要先判断 generated_map[0][0] == 1，此时不可达数就是 N*N（没有任何格子可达）。
• 洪水填充（Flood Fill）思想： 本题本质就是"从一个种子点扩散标记连通区域"，和岛屿数量完全同源，区别只在于本题计数的是"没被标记的部分"。
• 更大的网格： 如果 N 很大且地图稀疏，可以用"并查集"或者只对边界做反向 BFS（从地图四条边的 0 反向扩散，判断哪些 0 与外部连通）来优化。

---

相关题目

• 200. 岛屿数量 — 洪水填充计数连通块
• 695. 岛屿的最大面积 — 洪水填充统计面积
• 130. 被围绕的区域 — 反向从边界 BFS 判断连通性