回家

题目描述

[](https://paste.ubuntu.com/p/DSg5bzrrjs/) 小 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

说明

对于所有数据,$1 \le n,m \le 9$。 2021.9.2 增添一组 hack 数据 by @囧仙