题目：迷宫出口（基础）

任务总览

题目描述

一天，Extense 在森林里探险时误入了一个迷宫。迷宫由 n × n 的格点组成，每个格点的值只有 0 或 ​1​：

• 0 表示该位置可以通行。
• 1 表示该位置不可通行。

Extense 只能朝 ​东、南、西、北​（即 ​上、下、左、右​）四个方向移动，他希望从 点 A 走到 ​点 B​，请判断是否可行。

• ​**如果 A 或 B 不能通行（值为 1），则直接输出 "NO"**​。
• ​**如果能够从 A 走到 B，则输出 "YES"，否则输出 "NO"**​。

输入格式

1. 第一行包含一个整数 n（1 ≤ n ≤ 100），表示迷宫的大小为 n × n。
2. 接下来 n 行，每行 n 个整数，表示迷宫的 0/1 矩阵。
3. 最后一行包含 四个整数ha la hb lb：
   • ha la 表示起点 A 的 行号 和 ​列号​。
   • hb lb 表示终点 B 的 行号 和 ​列号​。
   • ​坐标从 1 开始​，即 (ha, la) 和 (hb, lb) 是 1-based 坐标。

输出格式

• 如果可以从 A(ha, la) 走到 B(hb, lb)，输出 ​**"YES"**​。
• 否则，输出 ​**"NO"**​。

输入输出示例

输入示例 1

3
0 1 1
0 0 1
1 0 0
1 1 3 3

输出示例 1

YES

题目分析

这道题是一个 ​经典的迷宫可达性问题​，可以使用 深度优先搜索（DFS） 或 广度优先搜索（BFS） 来解决。

解法 1：深度优先搜索（DFS）

1. ​从起点开始递归搜索​：
   • 如果遇到 边界 或 ​**障碍物（1）**​，直接返回。
   • 如果到达终点，直接返回 "YES"。
   • 标记已访问的点，防止重复搜索。
   • 尝试向 上、下、左、右 四个方向进行递归搜索。
2. ​时间复杂度​：
   • 由于最多有 n² 个格点，每个点最多访问一次，​**时间复杂度为 O(n²)**​。

解法 2：广度优先搜索（BFS）

1. ​使用队列（Queue）进行层次遍历​：
   • 初始时，将起点 (ha, la) 放入队列。
   • 每次从队列取出当前坐标 (x, y)，尝试向 四个方向 移动：
     • 如果该方向可以通行且未访问过，则加入队列。
   • 如果搜索过程中找到了 (hb, lb)，则返回 "YES"。
   • 如果队列为空仍未找到终点，返回 "NO"。
2. ​时间复杂度​：
   • 由于 BFS 逐层扩展，每个点最多访问一次，​**时间复杂度同样为 O(n²)**​，但 BFS 适用于 最短路径 问题。

时间复杂度分析

​如果需要找到最短路径，BFS 更优​，但本题只需判断可达性，DFS 和 BFS 都可行。