2367. 海上营救
1000ms
256MB
简单
广度优先搜索
BFS
题目描述
海上巡逻队收到了求救信号，经确认信号由“大山号”发出。时间就是生命，巡逻队必须尽快赶到那里。
通过导航卫星的侦测，巡逻队获得了一张海洋图。地图上这块区域被划分成 $n \times n$ 个方格区域，其中：
- `*` 表示岛屿（不可通行）。
- `.` 表示海洋（可通行）。
巡逻队当前处于起点位置 $(1, 1)$。船只航行中只能从一个区域移动到相邻的 8 个区域（即上、下、左、右以及 4 个对角线方向）。
请计算巡逻队航行到大山号所在位置的最短距离（每移动到一个相邻区域距离增加 1）。如果无法到达，输出 `-1`。
输入格式
- 第一行包含一个正整数 $n$ ($1 \le n \le 50$)，表示海洋图的大小。
- 接下来 $n$ 行，每行包含一个长度为 $n$ 的字符串，表示海洋图的每一行（仅由 `.` 和 `*` 组成）。
- 最后一行包含两个正整数 $x$ 和 $y$ ($1 \le x, y \le n$)，表示大山号所在的行坐标和列坐标（1-indexed）。
输出格式
- 输出一个整数，表示巡逻队到大山号的最短距离；若无法到达，输出 `-1`。
样例 1
输入 (Input)
4 .... .**. ..*. *... 4 4
输出 (Output)
4
- 对于 $100\%$ 的数据：$1 \le n \le 50$，大山号坐标满足 $1 \le x, y \le n$。
- 起点 $(1, 1)$ 和终点 $(x, y)$ 保证在地图范围内。
- **算法提示**：
本题为标准的**八连通网格图最短路**问题，使用**广度优先搜索（BFS）**求解：
1. 将输入的 1-indexed 终点坐标 $(x, y)$ 转换为 0-indexed 的数组下标 $(x-1, y-1)$。
2. 队列中除了记录当前位置 $(r, c)$ 外，还需要记录从起点出发到达当前位置的步数 `dist`。
3. 每次出队一个位置，向其**八个方向**扩展（上、下、左、右、左上、右上、左下、右下）。
4. 若相邻位置在网格范围内、不是岛屿 `*` 且未被访问过，则将其标记为已访问并入队，步数加 1。
5. 首次到达目标点时即可直接返回当前步数；若队列为空仍未到达，说明无法到达，输出 `-1`。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功