题目内容

你是一名游戏开发工程师，需要为一款楼内救人小游戏实现寻路逻辑。游戏场景是一栋两层建筑，每一层都是 $m$ 行 $n$ 列的网格，整体可以看作一个 $m \times n \times 2$ 的立体地图。地图中的每个格子用以下整数表示：

• 0：空地，允许通行。
• 1：墙壁，不允许通行。
• 2：起点，整个地图中恰好出现一次，可以在任意一层。
• 3：终点，整个地图中恰好出现一次，可以在任意一层，也可能与起点位于同一层。
• 4：楼梯，每一层恰好出现一次，两层各有一个楼梯。起点、终点和楼梯所在的位置互不重叠。

玩家从起点所在格子出发，每一步可以在同一层内向上、下、左、右四个方向移动一格，不能移动到墙壁所在格子。当玩家位于某层的楼梯格子上时，还可以消耗 1 步移动到另一层的楼梯格子。除这种情况外，玩家无法跨楼层移动。

目标是求出从起点到终点所需的最少步数。如果不存在从起点到终点的可达路径，则返回 -1。

约束条件： m 和 n 均为整数，满足 $2 \le m, n \le 256$。

输入描述

第一行包含两个整数 m 和 n，分别表示每层楼的行数和列数。

接下来的 m 行，每行包含 n 个整数，表示第一层的地图。

再接下来的 m 行，每行包含 n 个整数，表示第二层的地图。

输出描述

输出一个整数，表示从起点到终点的最短路径步数；如果无法到达终点，则输出 -1。

样例1

输入

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

输出

2

说明

起点位于第一层第 0 行第 0 列，终点位于第一层第 0 行第 2 列。

第一层第 0 行第 1 列是空地 0，可以通行。因此最短路径为从起点向右移动两次到达终点，共 2 步。

样例2

输入

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

输出

5

说明

起点在第一层第 0 行第 0 列，先向右到达第一层楼梯，用 1 步。

从第一层楼梯跨到第二层楼梯，再用 1 步。

第二层楼梯位于第 0 行第 1 列，终点位于第 2 行第 0 列。从第二层楼梯向下到第 1 行第 1 列，再向下到第 2 行第 1 列，最后向左到达终点，用 3 步。

因此总步数为 5，输出 5。

样例3

输入

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

输出

-1

说明

起点在第一层第 0 行第 0 列。

它的右侧第 0 行第 1 列是墙壁 1，下方第 1 行第 0 列也是墙壁 1，并且起点不在楼梯上，因此无法向任何方向移动。

所以不存在到达终点的路径，输出 -1。

样例4

输入

2 2
2 4
0 0
4 3
0 0

输出

3

说明

这是 2 行 2 列的最小规模样例。

起点在第一层第 0 行第 0 列，第一层楼梯在第 0 行第 1 列。

路径为：向右走到第一层楼梯，用 1 步；跨到第二层第 0 行第 0 列的楼梯，再用 1 步；最后向右到达第二层第 0 行第 1 列的终点，用 1 步。总步数为 3。