题目描述

马里奥位于一个 $n\times m$ 的方格地图中。地图中的每个方格可能是空地、障碍物、起点、终点或宝藏。马里奥每一步可以向上、下、左、右相邻的方格移动，不能进入障碍物。

马里奥需要从起点出发，先到达任意一个宝藏方格，再到达终点。在取得宝藏之前，不能进入终点。

请计算完成任务所需的最少步数。

输入格式

第一行包含两个整数 $n$ 和 $m$。

接下来 $n$ 行，每行包含 $m$ 个整数，表示地图：

• $0$ 表示空地；
• $1$ 表示障碍物；
• $2$ 表示起点；
• $3$ 表示终点；
• $4$ 表示宝藏。

地图中恰好有一个起点和一个终点，并且至少有一个宝藏。

输出格式

输出一个整数，表示完成任务所需的最少步数。

4 5
2 0 1 0 4
0 0 1 0 0
1 0 0 0 1
4 0 1 0 3

7

数据范围与提示

• $1 \le n,m \le 800$
• 保证至少存在一条符合要求的路线