Moveable Maze

You are playing a puzzle game on a grid with $R$ rows and $C$ columns. Each square has a black dot at its centre, and black lines may extend from that dot toward some of its north, east, south, and west neighbours (possibly none of them, possibly all four).

Your piece starts at the centre of the square in row $i_1$, column $j_1$, and you want to move it to the centre of the square in row $i_2$, column $j_2$, using as few turns as possible.

A turn has two parts, and either part may be skipped:

1. Rotation: you may pick any one square of the grid and rotate it 90 degrees, clockwise or counterclockwise. All of that square's lines rotate together.
2. Movement: you may move your piece from the centre of its current square to the centre of a neighbouring square, as long as the piece never leaves the black lines. Concretely, you may move from square $A$ to a neighbouring square $B$ only if $A$ has a line pointing toward $B$ and $B$ has a line pointing back toward $A$.

Print the minimum number of turns needed to move the piece from $(i_1, j_1)$ to $(i_2, j_2)$. It is guaranteed that the destination is reachable.

The input contains several test cases.

The first line of each test case contains two integers $R$ and $C$ ($1 \le R, C \le 20$).

The second line contains four integers $i_1$, $j_1$, $i_2$, $j_2$ ($1 \le i_1, i_2 \le R$ and $1 \le j_1, j_2 \le C$): the starting row and column, then the destination row and column.

Each of the next $R$ lines describes one row of the grid, from north (top) to south (bottom). Every such line contains exactly $C$ space-separated tokens describing that row's squares from west (left) to east (right). Each token is one of:

• the single character x, meaning the square has no line to any neighbour; or
• a string made of some of the characters N, E, S, W (each appearing at most once), where N, E, S, W mean the square has a line toward its north, east, south, or west neighbour respectively.

It is guaranteed that the piece can be moved from $(i_1, j_1)$ to $(i_2, j_2)$.

The input ends with a line containing 0 0, which must not be processed as a test case.

For each test case, print a single line containing one integer: the minimum number of turns required to move the piece from $(i_1, j_1)$ to $(i_2, j_2)$.

Rotating a square affects only that square, but you may rotate any square on the board (not only the one your piece is on), so you can prepare distant squares in advance. Because rotation and movement can happen in the same turn, aligning a path and walking along it can overlap.

For a $4 \times 2$ board where the piece starts in row 1, column 1 and must reach row 4, column 1, one optimal sequence of 5 turns is:

1. Rotate square $(2,2)$ clockwise, then step to $(1,2)$.
2. Rotate square $(3,2)$ counterclockwise, then step to $(2,2)$.
3. Rotate square $(3,2)$ counterclockwise, then step to $(3,2)$.
4. Rotate square $(3,1)$ clockwise, then step to $(3,1)$.
5. Rotate square $(3,1)$ clockwise, then step to $(4,1)$.