编程介的小学生 2017-08-31 03:23 采纳率: 20.5%
浏览 830
已采纳

Alice Madness Return

Recently there is a new game called <>. In this game, Alice was trapped in the wonderland by some evil spirits and she also lost her memory. The player need to help Alice find her memory and escape from wonderland.

The chess board
Now Alice is facing a big door which is locked. If she wants to open the door, she must pass a strange maze on a chess board with size m*n. There is a pawn controlled by Alice, and there is a mirror pawn indirectly controlled by Alice. In each turn, Alice can move her own pawn 1 step to one of the four direction (north, south, west, east). At the same time, the mirror pawn will also move 1 step in opposite direction. Since there are 2 exits, Alice must find a way to make her pawn and the mirror pawn reach both the 2 exits simultaneously so that she can open the door.

This game is not easy because there are 2 kinds of chess pieces on the chess board which are listed below:
Rook: You can consider the Rook as a heavy stone so that nobody can step into the grid occupied by a Rook. The Rook itself will never move.
Knight: There is only one Knight on the chess board. Since the Knight is very dangerous, both Alice's pawn and the mirror pawn cannot be caught by the Knight (it means they meet in the same grid), or they will be killed. At first the Knight stands in a grid, facing one of the four direction. In each turn, after Alice and the mirror pawn has moved, the Knight will also move 1 step to the direction he is facing. If he is blocked by a Rook or he is on the boundary of the board, he will turn around (i.e turn to north if he is facing south) instead of moving.
Besides, there are some memory pieces of Alice on the chess board. Alice must control her own pawn to collect all the memory pieces before she leave the maze. There are at most 5 memory pieces on the chess board.
Now it's your job to help Alice find a way to collect all her memory and open the door as soon as possible.

Notice:
Any two chess pieces cannot occupy the same grid but the Knight can move into grid occupied by Alice or the mirror and in that situation he will kill them. You can consider the exit as empty grid so that Knight can pass the exit.
In each turn, Alice must move her own pawn and cannot move out of the chess board. If she cannot move, she will die.
After Alice's move, the mirror will move, but if the mirror is blocked by any chess piece(i.e the mirror is blocked by a Rook) or it is forced to move out of the chess board, then the mirror will stay unmoved.
Once Alice and the mirror reach the 2 exits, the door will open and the Knight cannot catch them after that. Of course, if the door has been open, Alice cannot get back to the chessboard to collect her memory any more.
Input

The input contains multiple test cases.
In each test case, fisrt there are two integers, m and n ( 1 <= m, n <=10 ) , which is the size of the chess board.
Then there are m lines each containing n characters. In these characters, '*' means empty grid, 'R' means Rook, 'K' means Kight, 'A' means Alice's pawn, 'B' means the mirror pawn, 'E' means exit, 'M' means memory piece.
Finally there is a line containing one character describing the initial direction the Knight is facing. 'N' means north, 'S' means south, 'W' means west, 'E' means east.
We guarantee that there are exactly 1 Knight, 2 exits, no more than 5 memory pieces on the chess board.

Output

For each test case, output one line with an integer which is the minimum number of turns Alice needed to collect all her memory pieces and open the door. If she cannot finish the task, output -1 instead.

Sample Input

6 6
BR*E


R*
**K*
R*
E**R*A
E
Sample Output

8

  • 写回答

1条回答

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

报告相同问题?

悬赏问题

  • ¥15 fpga自动售货机数码管(相关搜索:数字时钟)
  • ¥20 Python安装cvxpy库出问题
  • ¥15 用前端向数据库插入数据,通过debug发现数据能走到后端,但是放行之后就会提示错误
  • ¥15 python天天向上类似问题,但没有清零
  • ¥30 3天&7天&&15天&销量如何统计同一行
  • ¥30 帮我写一段可以读取LD2450数据并计算距离的Arduino代码
  • ¥15 C#调用python代码(python带有库)
  • ¥15 活动选择题。最多可以参加几个项目?
  • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型
  • ¥15 vs2019中数据导出问题