30367번 - Break a Prison 다국어

Jennifer is a software engineer at a Tech company. Her company decided to join ICPC (Inter-Company Prison breaking Contest) and she was chosen as a representative of the company.

In ICPC, every participant needs to escape from a prison. The prison can be represented as an $n \times m$ grid i.e. it has $n$ rows and $m$ columns of rooms. The room in the $i$-th row and $j$-th column in the prison is denoted as room $(i, j)$. Two rooms $(i_1, j_1)$ and $(i_2, j_2)$ are adjacent if and only if $|i_2 - i_1| + |j_2 - j_1| = 1$. Weirdly, there is an unlocked door between each pair of adjacent rooms. Some rooms in the prison are under surveillance. Participants can move to a room only if it's not under surveillance. A participant will start from a room. The goal of all participants is to reach an exit. It's guaranteed that the room with the exit and the room that participants start from are not under surveillance.

To show talents in the company, the CEO asked Jeniffer not to turn right during the contest. In other words, there should not be any two consecutive moves between rooms that fulfill the following condition.

Condition: Given that Jeniffer moved from room $(i_1, j_1)$ to $(i_2, j_2)$, and then she moved to room $(i_3, j_3)$. Then, $(i_2 - i_1) \times (j_3 - j_2) - (j_2 - j_1) \times (i_3 - i_2) = -1$ holds.

Figure B.1. Example of allowed and denied moves

For example, in figure B.1., if the last move is along the dashed arrow, you cannot move downward but you can move the other three directions.

Note that U-turns are allowed with this condition.

As a Jeniffer's colleague, your mission is to write a program to find the minimum number of moves between rooms to reach the exit for her.

The input consists of a single test case in the following format.

$n$ $m$

$c_{1,1}c_{1,2}\dots c_{1,m}$

$c_{2,1}c_{2,2}\dots c_{2,m}$

$\vdots$

$c_{n,1}c_{n,2}\dots c_{n,m}$

$n$ and $m$ represent the size of the prison, each of which is an integer between $2$ and $500$. $c_{i,j}$ ($1 \le i \le n$, $1 \le j \le m$) is a character that describes the status of a room in the $i$-th row and $j$-th column. The character is either

• ‘S' which means a start room for a participant,
• ‘E' which means a room with an exit,
• ‘.' which means the room is not under surveillance, or
• ‘#' which means the room is under surveillance.

It is guaranteed that ‘S' and ‘E' appear exactly once in the input respectively.

Print the minimum number of moves between rooms for Jenniffer to reach the exit. If she cannot reach the exit, print $-1$.

In Sample Input 3, one of the optimal routes is below.

Figure B.2. The optimal route in Sample Input 3