2366. 棋盘寻宝
1000ms
256MB
简单
广度优先搜索
BFS
题目描述
在一个 $n \times m$ 的网格棋盘中，分布着侍卫和宝藏。寻宝者从棋盘左上角 $(1, 1)$ 位置出发寻找宝藏。
如果在寻宝过程中能够避开所有侍卫到达宝藏所在的位置，则输出 `YES`；否则输出 `NO`。
**注意**：起点 $(1, 1)$ 处不一定安全（即起点也有可能存在侍卫）。
输入格式
- 输入第一行包含两个非零整数 $n$ 和 $m$ ($1 < n, m \le 100$)，分别表示棋盘的行数和列数。
- 接下来 $n$ 行，每行包含 $m$ 个字符，字符的具体含义如下：
- `.`：代表可以安全通行的方格。
- `#`：代表有侍卫驻守的方格（不可通行）。
- `*`：代表宝藏所在的位置。
输出格式
- 如果能够成功避开侍卫找到宝藏，输出 `YES`；否则输出 `NO`。
样例 1
输入 (Input)
5 6 ..#... ...#.. ...#.. #..... ###..*
输出 (Output)
YES
样例 2
输入 (Input)
4 4 #... .... ...* ....
输出 (Output)
NO
- 对于 $100\%$ 的数据：$1 < n, m \le 100$。
- **算法提示**：
本题为标准的迷宫连通性判定问题。
1. 首先读入矩阵，并找到宝藏 `*` 的坐标。如果左上角起点坐标 `(0, 0)` 处为 `#`，则直接无法开始移动，输出 `NO`。
2. 从起点 `(0, 0)` 开始，利用队列（Queue）进行 BFS 或利用递归进行 DFS，只允许在相邻的非 `#` 格子（即 `.` 和 `*`）之间进行上下左右四个方向的移动。
3. 用一个二维布尔数组 `visited` 记录已被访问的方格，避免死循环。
4. 如果能遍历到 `*` 的坐标，则输出 `YES`，否则输出 `NO`。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功