Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 2279
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

9

Contest: A Great Beloved and My Gate to Freedom
There is a cx, there is a love_cx.

Author: JIANG, Yanyan
Source: JIANG, Yanyan's Contest #2
Submit    Status