움직이는 미로

$R$개의 행과 $C$개의 열로 이루어진 격자에서 진행하는 퍼즐 게임이다. 각 칸의 중앙에는 검은 점이 있고, 그 점에서 북쪽, 동쪽, 남쪽, 서쪽 이웃 칸 방향으로 검은 선이 뻗어 있을 수 있다(하나도 없을 수도, 네 방향 모두일 수도 있다).

말은 처음에 $i_1$행 $j_1$열 칸의 중앙에 있으며, 이 말을 $i_2$행 $j_2$열 칸의 중앙으로 가능한 한 적은 턴 수로 옮기는 것이 목표다.

한 턴은 다음 두 단계로 이루어지며, 각 단계는 생략할 수 있다.

1. 회전: 격자의 임의의 칸 하나를 골라 시계 방향 또는 반시계 방향으로 90도 회전시킬 수 있다. 그 칸의 모든 선이 함께 회전한다.
2. 이동: 말을 현재 칸의 중앙에서 이웃한 칸의 중앙으로 옮길 수 있는데, 말이 검은 선을 벗어나서는 안 된다. 즉, 칸 $A$에서 이웃한 칸 $B$로 이동하려면 $A$에 $B$를 향하는 선이 있고 $B$에도 $A$를 향하는 선이 있어야 한다.

말을 $(i_1, j_1)$에서 $(i_2, j_2)$로 옮기는 데 필요한 최소 턴 수를 출력하라. 목적지에 도달할 수 있음이 보장된다.

입력은 여러 개의 테스트 케이스로 이루어진다.

각 테스트 케이스의 첫 줄에는 두 정수 $R$와 $C$가 주어진다 ($1 \le R, C \le 20$).

둘째 줄에는 네 정수 $i_1$, $j_1$, $i_2$, $j_2$가 주어진다 ($1 \le i_1, i_2 \le R$, $1 \le j_1, j_2 \le C$). 각각 시작 칸의 행과 열, 그리고 목적지 칸의 행과 열이다.

이어지는 $R$개의 줄은 격자의 각 행을 북쪽(위)에서 남쪽(아래) 순서로 나타낸다. 각 줄에는 그 행의 칸들을 서쪽(왼쪽)에서 동쪽(오른쪽) 순서로 나타내는 문자열이 정확히 $C$개, 공백으로 구분되어 주어진다. 각 문자열은 다음 중 하나다.

• 문자 x 하나: 그 칸에는 어떤 이웃 방향으로도 선이 없다.
• N, E, S, W 중 일부로 이루어진 문자열(각 문자는 최대 한 번 등장): 각각 그 칸에 북쪽, 동쪽, 남쪽, 서쪽 이웃을 향하는 선이 있음을 뜻한다.

말을 $(i_1, j_1)$에서 $(i_2, j_2)$로 옮길 수 있음이 보장된다.

입력의 끝은 0 0으로 이루어진 줄로 표시되며, 이 줄은 테스트 케이스로 처리하지 않는다.

각 테스트 케이스마다, 말을 $(i_1, j_1)$에서 $(i_2, j_2)$로 옮기는 데 필요한 최소 턴 수를 정수 하나로 한 줄에 출력하라.

한 칸을 회전시키면 그 칸에만 영향을 주지만, 말이 놓인 칸뿐 아니라 격자의 어떤 칸이든 회전시킬 수 있으므로 멀리 있는 칸을 미리 준비해 둘 수 있다. 또한 회전과 이동은 같은 턴 안에서 일어날 수 있어, 경로를 맞추는 작업과 그 경로를 따라 걷는 작업이 겹칠 수 있다.

$4 \times 2$ 격자에서 말이 1행 1열에서 시작해 4행 1열에 도달해야 할 때, 최적의 5턴 순서 중 하나는 다음과 같다.

1. 칸 $(2,2)$를 시계 방향으로 회전시키고 $(1,2)$로 이동한다.
2. 칸 $(3,2)$를 반시계 방향으로 회전시키고 $(2,2)$로 이동한다.
3. 칸 $(3,2)$를 반시계 방향으로 회전시키고 $(3,2)$로 이동한다.
4. 칸 $(3,1)$을 시계 방향으로 회전시키고 $(3,1)$로 이동한다.
5. 칸 $(3,1)$을 시계 방향으로 회전시키고 $(4,1)$로 이동한다.