题目内容

你是一名游戏开发工程师，正在设计一款楼内救人的小游戏。游戏地图是一个 $m \times n \times 2$ 的 2 层楼地图，每个格子代表一个区域：

• 0：空地（可以通行）
• 1：墙壁（不可通行）
• 2：起点（有且只有1个，在任意一层）
• 3：终点（有且只有1个，在任意一层，可能与起点在同一层）
• 4：楼梯（每层楼有且只有1个）

玩家从起点出发，每次只能上下左右移动一格，不能穿过墙壁。目标是找到从起点到终点救人的最短路径（以步数计），并返回路径长度。

注意：

1. 通过楼梯算 1 步，除了通过楼梯外，无法跨楼层移动。
2. 如果无法到达终点救人，返回 -1。
3. 起点、终点、楼梯所在位置不重叠。

输入描述

第 1 行输入 $m$ $n$（$2 \leq m, n \leq 256$）

接下来的第 2 ~ $m+1$ 行，每行有 $n$ 个整数 $x$ 代表第 1 层地图

第 $m+2$ ~ $2*m+1$ 行，每行有 $n$ 个整数 $x$ 代表第 2 层地图

输出描述

返回路径长度，如无法到达终点救人，返回 -1

样例1

输入

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

输出

9

说明

从第一层的 (0,0) 出发，经过 (0,1) -> (0,2) -> (1,2) -> (2,2) -> (2,1) 到楼梯 5 步，上楼 1 步，第二层的 (1,0) -> (1,1) -> (1,2) -> (2,2) 到目标 3 步，共 9 步。

样例2

输入

2 2
2 0
4 1
4 1
1 3

输出

-1

说明