← 返回题目
题库练习 回家
← 上一题 下一题 →

A2813 | 回家

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

小 H 在一个划分成了 $n \times m$ 个方格的长方形封锁线上。 每次他能向上下左右四个方向移动一格（当然小 H 不可以静止不动）， 但不能离开封锁线。 刚开始时他有满血 $6$ 点，每移动一格他要消耗 $1$ 点血量。一旦小 H 的血量降到 $0$， 他将被淘汰。 他可以沿路通过拾取鼠标来补满血量。只要他走到有鼠标的格子，他不需要任何时间即可拾取。格子上的鼠标可以瞬间补满，所以每次经过这个格子都有鼠标。就算到了某个有鼠标的格子才淘汰， 他也不能通过拾取鼠标补满 HP。 即使在家门口淘汰， 他也不能算完成任务回到家中。

地图上有五种格子：

0：障碍物。

1：空地， 小 H 可以自由行走。

2：小 H 出发点， 也是一片空地。

3：小 H 的家。

4：有鼠标在上面的空地。

小 H 能否成功回家？如果能， 最短需要多长时间呢？

输入格式

第一行两个整数 $n,m$， 表示地图的大小为 $n \times m$。

下面 $n$ 行， 每行 $m$ 个数字来描述地图。

输出格式

一行， 若小 H 不能回家， 输出 -1，否则输出他回家所需最短时间。

输入输出样例

输入 #1
3 3
2 1 1
1 1 0
1 1 3
输出 #1
4
C++ 编辑器
输入
输出