2344. 营救行动
1000ms
256MB
简单
广度优先搜索
BFS
题目描述
一只野生小鹿被困在了一个大小为 $n \times n$ 的家园的 $(n, n)$ 位置。内格从 $(1, 1)$ 位置出发去解救小鹿。
请编写程序，计算内格是否可以成功解救小鹿。内格只能在**上下左右**四个方向移动。
**要求：使用广度优先搜索（BFS）算法实现。**
输入格式
- 第一行包含一个正整数 $n$ ($2 \le n \le 10$)，表示方格图的大小。
- 接下来 $n$ 行，每行包含 $n$ 个字符（字符之间用空格隔开）：
- `.` 表示可通行的道路。
- `#` 表示不可通行的障碍物。
输出格式
- 输出一行。若能够成功解救，输出 `YES`；否则输出 `NO`。
样例 1
输入 (Input)
7 . # # . . . . . # . . . . . . . . . # . . . . . . . . # # # . # . . . # # # . # # . . # # # . . . ---->>>>>🦌在(n,n)
输出 (Output)
YES
- 对于所有数据：$2 \le n \le 10$。
- **输入读取提示**：
输入字符之间可能有空格。在 C++ 中，如果直接使用 cin >> char 读入每个格子的状态，`cin` 会自动跳过空格和换行符，这能完美避免因为空格导致的数据错位问题。
- **算法提示**：
本题要求使用**广度优先搜索（BFS）**。
1. 建立一个队列，将起点 $(0, 0)$ 入队，并标记为已访问。
2. 每次从队首取出一个点，判断它是否为终点 $(n-1, n-1)$。如果是，则表示可以到达，输出 `YES`。
3. 如果不是，向其上下左右四个方向拓展。若相邻的点在矩阵范围内、不是障碍物且未被访问过，则将其入队并标记为已访问。
4. 如果队列为空时仍未到达终点，说明无法连通，输出 `NO`。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功