Alice Madness Return
Time Limit: 3 Seconds
Memory Limit: 131072 KB
Recently there is a new game called <<Alice Madness Return>>. 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.
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.
- 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.
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.
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.
Author: HUANG, Qiao
Contest: ZOJ Monthly, September 2011