The Little Beaver is in a maze. The maze is made up of two floors, each with its own grid of obstacles.小海狸被困在了一个迷宫里。这个迷宫由两层组成，每层都有自己的障碍网格。
The Little Beaver can move between two adjacent cells within one floor if there is no wall between the cells; this takes one second.小海狸可以在同一层内相邻的两个格子之间移动，前提是这两个格子之间没有墙；这需要花费一秒钟。
The Little Beaver can also use her magic wand to move to the corresponding cell of the other floor; this takes five seconds.小海狸还可以用她的魔法棒移动到另一层对应的单元格；这需要五秒钟。
For example, if the Little Beaver is in cell A, there are three possible moves:例如，如果小海狸在 A 单元格，那么有三种可能的移动方式：
1. Move left. This move takes 1 second.1. 向左移动。此动作耗时 1 秒。
2. Move down. This move takes 1 second.2. 向下移动。此动作耗时 1 秒。
3. Move to the corresponding cell of the other floor. This move takes 5 seconds.3. 移动到另一层对应的单元格。此移动耗时 5 秒。
The Little Beaver starts at cell A and wants to reach cell B as soon as possible. 小海狸从 A 单元格出发，想要尽快到达 B 单元格。
Question:问题:
What is the shortest time needed for the Little Beaver to reach cell B, if starting from cell A?如果小海狸从 A 单元格出发，那么它到达 B 单元格所需的最短时间是多少？
A. 16
B. 17
C. 18
D. 20
Explanation 解释
Answer: 答案:
18
Explanation: 解释:
The given problem is a shortest path problem. There are different approaches to obtain the solution, one of which is to apply Dijkstra’s algorithm to find the shortest path from A to B. The image below shows the lengths of the optimal paths to all cells if starting from A.给定的问题是一个最短路径问题。有多种方法可以得到解决方案，其中之一是应用迪杰斯特拉算法来找出从 A 到 B 的最短路径。下面的图片展示了从 A 出发到达所有单元格的最优路径长度。
One can see that the length of the shortest path to B is 18. One of the possible optimal paths is the following: 可以看出，到 B 点的最短路径长度为 18。其中一条可能的最优路径如下：
Answer D (20) corresponds to the optimal path when moving only within one floor. Answer A (16) corresponds to the lower bound of the time to reach B from A if going via the other floor and assuming there are no walls (i. e. [Manhattan distance from A to B] + [time to move between floors]).答案 D（20）对应的是仅在一楼内移动时的最优路径。答案 A（16）对应的是从 A 到 B 经过另一层楼且假设没有墙壁（即从 A 到 B 的曼哈顿距离加上楼层间移动的时间）时的最短时间下限。
点击右侧文字，可获得更多在线练习题资源：>>> Bebras在线水平测试
Bebras新赛季备赛已开启，扫码领取Bebras真题资料⇓
欢迎咨询【Bebras专业辅导课程】
（Bebras每日一练部分展示）
