CJDF03｜迷宫能否到达 题解

核心算法

把每个可通行格看成结点，从起点做四方向 DFS。

思路推导

对当前格依次尝试四个相邻格，只进入边界内、非障碍且未访问的格。访问终点即可返回成功。

正确性说明

DFS 会遍历起点所在的整个可通行连通区域。终点在该区域中当且仅当它能被访问，所以输出正确。

复杂度

时间复杂度 $O(nm)$，空间复杂度 $O(nm)$。

易错点

• 先判断边界再访问数组；
• 必须使用访问标记，否则会在相邻格间来回递归；
• 四方向不包含斜向移动。