In the Mirror
Time Limit: 2 Seconds Memory Limit: 32768 KB
Background
We continued going in the labyrinth. Suddenly, we went to a room with all the lights on, and I saw some bats staring at some mirror. Of course, the bats can eat us...
CX screamed at once! We mustn't be eaten by the bats! Help!
Problem
The room is N rows and M columns (N, M<=10). There're 4 kinds of bats: "^", "v", "<", ">", stands for 4 kinds of bats facing 4 directions. There are some obstacles ("#") in the room. And there're 2 kinds of mirror: "/", "\". Number of mirror will not exceed 10. Bats can find CX and me through mirrors. You can assume that bats has a speed of infinite, when it see us, it will kill us immediately.
I can move to an adjacent square by taking 1 unit of time, and rotate any mirror at any grid by taking 1 unit of time, too. How I can get out of the room?
Input
This problem contains multiple test cases.
Each test case begins with two integers N and M. Next N lines contain the map. "S" is the Start Point, and "E" is the End Point. There's exact one S and one E in the room.
Output
For each test case, output the shortest time I can escape. If no solution existed, output "poor".
Sample Input
5 5 S.v.. ..... ..... ../.. ....E
Sample Output
9Submit
Source: JIANG, Yanyan's Contest #2