Skip to content

1032: 泷的旅途

题目

题目描述

深秋季节,天气渐凉,三叶由于最近期中考试太过忙碌,连续熬夜,不慎染上了感冒。泷听说后,非常担忧,于是决定出发去看三叶。已知泷和三叶处在一个矩形网格上,泷每次可以上下左右移动一格,但是他不能越过边界。要知道,泷虽然擅长体育,但是他的体力毕竟是有限的,已知泷的初始体力为6点,他每移动一格就要耗费一点体力,如果体力耗尽他就不能继续前进。幸运的是,三叶预想到了这一点,于是她提前请人帮忙在一些网格上放置了亲手做的便当。如果泷到达了放有便当的网格,那么他的体力值可以瞬间得到补充,恢复为6。值得注意的是,如果泷到达有便当的网格时体力已经为0,则他连吃饭的力气都没有了,就视为不可到达。如果他到达终点时体力为0,也视为不可到达。已知泷每走一格耗时为1,网格上的有些点上有不可逾越的建筑物,不能通过。

  • 数字 0:建筑物。(不允许通过)
  • 数字 1:空地,泷可以自由行走。
  • 数字 2:泷出发点, 也是一片空地。(行程起点)
  • 数字 3:三叶所在地。(行程终点)
  • 数字 4:便当所在地。

以标号为2的网格为起点,标号为3的网格为终点,问,泷能否见到三叶?如果能, 最短需要多长时间呢?

输入格式

第一行两个数字,网格的行数和列数,n,m。

第2至n+1行,描述整个网格。

输出格式

如果可到达,输出最短用时,否则输出-1。

样例输入

3 3 2 1 1 1 1 0 1 1 3

样例输出

4

数据范围

  • 对于70%的数据 $0<n,m \le 20$;
  • 对于30%的数据 $0<n,m \le 300$.

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!