编程介的小学生 2017-05-03 04:25 采纳率: 20.5%
浏览 810
已采纳

Mummy Maze

Mummy Maze is one of my favourite games of Fantasy Games series. In the game you, a fearless explorer, are located in a treacherous chamber of an Egyptian pyramid. The pyramid is riddled with traps, infested with deadly scorpions, and haunted by relentless mummies. There is only one exit in the chamber where you can get away. Your objective is to get to the exit without getting caught by the scorpions or mummies, and finally claim the treasure waiting at the top of the pyramid.

Let's consider a simplified game mode following.

Scene and Roles

A maze of N * N squares is given. Some walls exist obstructing some pairs of adjacent squares. The borders of the maze are also closed walls except a gap which is the only one exit.
A gate may exist obstructing two adjacent squares in the maze. If there is a gate, the maze will also have a key on a certain square. Gate is never located at the border.
You, the explorer, are located on one square of the maze at the initial situation.
There are one or two mummies located on other squares different from your starting point at the initial situation.
Movements

In each turn, you, the explorer, can move to a directly adjacent square (no wall obstructing). Diagonal moves are not allowed. You can also choose to pass this turn so that the explorer will stay there without movement.
Aftar your turn, it is the mummies' turn. A mummy can move twice at most. For each move, if the mummy can move horizontally and get closer to you, it will do so. If the mummy can't move horizontally, but can move vertically and get closer to you, it will do that instead. Otherwise, it will stay there for this turn. Mummies move simultaneously.
Two mummies may move to the same place. Then they will turn into only one mummy. (or say that one of them is lost, which one lost is insignificant)
Gate and Key

The gate is closed at the initial situation.
The gate can be opened or closed immediately by moving onto the key square. The key can be triggered either by you or a mummy.
If two mummies step on the key simultaneously, the key is triggered twice.
Goal

If you and a mummy are located on the same square, then you are caught.
Your objective is to get away the maze from the exit at the border without getting caught by the mummies.
Now is your task. What is the minimum number of turns you need to flee the maze?

Input

Input contains multiple test cases. Each test case starts with an integer N (1 <= N <= 10) in one line, which is the size of the maze. Then N * 2 + 1 lines follow, each line consists of N * 2 + 1 characters, which shows the figure of the maze. The characters of odd line and odd column is always '+'. The characters of odd line and even column or of even line and odd column is either '-' or '|' when it specifies a wall, is ' ' when it specifies no wall or an exit at the border, or is 'G' when it specifies a gate. The characters of even line and even column is ' ', 'E', 'M' or 'K' which specifes an empty square, starting poing of the explorer, starting poing of a mummy or a key respectively.

Output

There is one line for each test case, which is the minimum number of turns you need to flee the maze. If you can't get away the maze, just output -1.

Sample Input

3
+-+ +-+
|M |

  • +-+ + | | |
  • +-+ + |E | +-+-+-+ 3 +-+ +-+ |M |
  • +-+ + |M | |
  • +-+ + |E | +-+-+-+ 3 +-+-+-+ | E |
  • +-+G+ | |K|
  • +-+ + | |M| +-+ +-+ 3 +-+-+-+ | E |
  • +-+G+ |K | |
  • +-+ + | |M| +-+ +-+ Sample Output

7
-1
-1
4

  • 写回答

1条回答 默认 最新

  • threenewbee 2017-05-17 15:53
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥50 树莓派安卓APK系统签名
  • ¥15 maple软件,用solve求反函数出现rootof,怎么办?
  • ¥65 汇编语言除法溢出问题
  • ¥15 Visual Studio问题
  • ¥20 求一个html代码,有偿
  • ¥100 关于使用MATLAB中copularnd函数的问题
  • ¥20 在虚拟机的pycharm上
  • ¥15 jupyterthemes 设置完毕后没有效果
  • ¥15 matlab图像高斯低通滤波
  • ¥15 针对曲面部件的制孔路径规划,大家有什么思路吗