ZOJ Problem Set - 2279
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!
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?
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.
For each test case, output the shortest time I can escape. If no solution existed, output "poor".
Author: JIANG, Yanyan
Source: JIANG, Yanyan's Contest #2