A22524.回家
普及-
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
小 H 在一个划分成了 n×m 个方格的长方形封锁线上。 每次他能向上下左右四个方向移动一格(当然小 H 不可以静止不动), 但不能离开封锁线。 刚开始时他有满血 6 点,每移动一格他要消耗 1 点血量。一旦小 H 的血量降到 0, 他将被淘汰。 他可以沿路通过拾取鼠标来补满血量。只要他走到有鼠标的格子,他不需要任何时间即可拾取。格子上的鼠标可以瞬间补满,所以每次经过这个格子都有鼠标。就算到了某个有鼠标的格子才淘汰, 他也不能通过拾取鼠标补满 HP。 即使在家门口淘汰, 他也不能算完成任务回到家中。
地图上有五种格子:
0
:障碍物。
1
:空地, 小 H 可以自由行走。
2
:小 H 出发点, 也是一片空地。
3
:小 H 的家。
4
:有鼠标在上面的空地。
小 H 能否成功回家?如果能, 最短需要多长时间呢?
输入格式
第一行两个整数 n,m, 表示地图的大小为 n×m。
下面 n 行, 每行 m 个数字来描述地图。
输出格式
一行, 若小 H 不能回家, 输出 -1
,否则输出他回家所需最短时间。
输入输出样例
输入#1
3 3 2 1 1 1 1 0 1 1 3
输出#1
4
说明/提示
对于所有数据,1≤n,m≤9。