#P14593. [Bulgarian 2023]path

[Bulgarian 2023]path

题目描述

给定一个 N×MN\times M 的网格,其中部分格子是障碍,不能进入。

初始时,你位于左上角格子 (1,1)(1,1),目标是到达右下角格子 (N,M)(N,M)。

对于每一个整数时刻 t≥1t\ge 1,你必须执行以下两种操作中的一种:

  • 停留:保持在当前格子不动。
  • 跳跃:向上、下、左、右四个方向之一,恰好移动 tt 个格子。跳跃的落点必须在网格内,且不能是障碍格;但跳跃过程中可以越过障碍格。

求最早能够到达右下角格子的时刻(即执行的最少操作次数)。如果无论如何都无法到达,输出 −1-1。

输入格式

第一行包含两个整数 N,MN,M,分别表示网格的行数和列数。

接下来 NN 行,每行包含一个长度为 MM 的字符串,描述网格:

  • # 表示障碍格,不能进入;
  • . 表示空格,可以进入。

输出格式

输出一个整数,表示能够到达右下角格子的最早时刻;如果无法到达,输出 −1-1。

数据范围

  • 1≤N,M≤1061\le N,M\le 10^6;
  • 1≤NM≤1061\le NM\le 10^6;
  • NN 和 MM 不同时为 11;
  • 左上角 (1,1)(1,1) 和右下角 (N,M)(N,M) 均为空格。

子任务

子任务 分值 NN MM NMNM
1 15 ≤5000\le 5000
2 10 =1=1 ≤106\le 10^6
3 25 ≤2000\le 2000 ≤2.5×105\le 2.5\times 10^5
4 40 ≤2.5×105\le 2.5\times 10^5
5 10 ≤106\le 10^6

只有通过某个子任务中的全部测试点,才能获得该子任务的全部分数。

样例输入 #1

1 6
..#...

样例输出 #1

4

样例解释 #1

  • 在时刻 t=1t=1,从格子 (1,1)(1,1) 向右跳 11 格,到达 (1,2)(1,2)。
  • 在时刻 t=2t=2 和 t=3t=3,停留在 (1,2)(1,2)。
  • 在时刻 t=4t=4,从 (1,2)(1,2) 向右跳 44 格,到达 (1,6)(1,6),途中可以越过障碍格 (1,3)(1,3)。

因此,最早在时刻 44 到达终点,答案为 44。