Description

The Robot Mobility Institute (RMI) is now trying to use robots to transport items. The robot is a sphere with a diameter of $1.6$ meters. During the trial phase, the robot is used to move cargo in a storeroom. The storeroom is an $N\times M$ grid, and some cells are immovable obstacles. The robot’s center is always on grid points. Of course, the robot must deliver the item to the designated location in the shortest time. The robot accepts the following commands:

• Move forward $1$ step (Creep);
• Move forward $2$ steps (Walk);
• Move forward $3$ steps (Run);
• Turn left (Left);
• Turn right (Right).

Each command takes $1$ second. Please compute the minimum time required for the robot to complete the task.

Input Format

The first line contains two positive integers $N,M\ (1\le N,M\le50)$. The next $N$ lines describe the storeroom layout: $0$ means no obstacle, and $1$ means an obstacle. Numbers are separated by a single space. Then one line contains $4$ integers and $1$ uppercase letter, which are the row and column of the top-left cell of the starting point and the target point, and the initial facing direction (east $\tt E$, south $\tt S$, west $\tt W$, north $\tt N$). There is a single space between numbers, and between numbers and the letter. The facing direction at the destination is arbitrary.

Output Format

Output one integer, the minimum time required for the robot to complete the task. If it is impossible to reach the destination, output $-1$.

9 10
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 1 0
7 2 2 7 S

12

Hint

Translated by ChatGPT 5