解题思路
将每个可通行格子看成图中的一个节点,节点状态为 (floor,x,y),其中 floor 表示楼层,x 和 y 表示坐标。
由于玩家每次移动一步的代价都是 1,包括通过楼梯跨楼层也算 1 步,所以可以使用 BFS 求最短路。
具体做法:
- 读入 2 层地图,找到起点 2、终点 3,以及两层楼的楼梯 4。
P5115.第3题-楼内救人
题目内容
你是一名游戏开发工程师,正在设计一款楼内救人的小游戏。游戏地图是一个 m×n×2 的 2 层楼地图,每个格子代表一个区域:
- 0:空地(可以通行)
- 1:墙壁(不可通行)
- 2:起点(有且只有1个,在任意一层)
- 3:终点(有且只有1个,在任意一层,可能与起点在同一层)
- 4:楼梯(每层楼有且只有1个)
玩家从起点出发,每次只能上下左右移动一格,不能穿过墙壁。目标是找到从起点到终点救人的最短路径(以步数计),并返回路径长度。
注意:
- 通过楼梯算 1 步,除了通过楼梯外,无法跨楼层移动。
- 如果无法到达终点救人,返回 -1。
- 起点、终点、楼梯所在位置不重叠。
输入描述
第 1 行输入 m n(2≤m,n≤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
说明
