#P14593. [Bulgarian 2023]path
[Bulgarian 2023]path
题目描述
给定一个 的网格,其中部分格子是障碍,不能进入。
初始时,你位于左上角格子 ,目标是到达右下角格子 。
对于每一个整数时刻 ,你必须执行以下两种操作中的一种:
- 停留:保持在当前格子不动。
- 跳跃:向上、下、左、右四个方向之一,恰好移动 个格子。跳跃的落点必须在网格内,且不能是障碍格;但跳跃过程中可以越过障碍格。
求最早能够到达右下角格子的时刻(即执行的最少操作次数)。如果无论如何都无法到达,输出 。
输入格式
第一行包含两个整数 ,分别表示网格的行数和列数。
接下来 行,每行包含一个长度为 的字符串,描述网格:
#表示障碍格,不能进入;.表示空格,可以进入。
输出格式
输出一个整数,表示能够到达右下角格子的最早时刻;如果无法到达,输出 。
数据范围
- ;
- ;
- 和 不同时为 ;
- 左上角 和右下角 均为空格。
子任务
| 子任务 | 分值 | |||
|---|---|---|---|---|
| 1 | 15 | |||
| 2 | 10 | |||
| 3 | 25 | |||
| 4 | 40 | |||
| 5 | 10 | |||
只有通过某个子任务中的全部测试点,才能获得该子任务的全部分数。
样例输入 #1
1 6
..#...
样例输出 #1
4
样例解释 #1
- 在时刻 ,从格子 向右跳 格,到达 。
- 在时刻 和 ,停留在 。
- 在时刻 ,从 向右跳 格,到达 ,途中可以越过障碍格 。
因此,最早在时刻 到达终点,答案为 。