미로

아래와 같이 정삼각형들로 이루어진 미로가 있다.

각 꼭짓점은 그림처럼 두 좌표 x, y로 나타낸다. 일부 간선에는 흰색 또는 검은색 원이 그려져 있다. 미로에서의 이동은 다음 두 규칙을 따른다.

• 원이 그려진 간선으로만 지나갈 수 있다.
• 지나가는 원의 색은 반드시 번갈아 나와야 한다. 즉, 흰색 원이 있는 간선을 지난 직후에는 검은색 원이 있는 간선을, 검은색 원이 있는 간선을 지난 직후에는 흰색 원이 있는 간선을 지나야 한다. 단, 가장 첫 번째 이동은 흰색과 검은색 중 어느 색으로 시작해도 된다.

입구에서 출구까지 가는 가장 짧은 경로의 길이를 구하여라. 경로의 길이는 지나간 간선(또는 원)의 개수로 정의한다. 그러한 경로는 항상 존재한다고 가정해도 된다.

첫째 줄에 미로의 너비 W와 높이 H가 주어진다 (1 ≤ W, H ≤ 500).

둘째 줄에는 네 정수 X1 Y1 X2 Y2가 주어진다 (0 ≤ X1, X2 ≤ W; 0 ≤ Y1, Y2 ≤ H). (X1, Y1)은 입구, (X2, Y2)는 출구의 좌표이다.

다음 2H+1개의 줄에는 간선의 정보가 주어진다. 이 줄들 중 홀수 번째 줄(1, 3, 5, …번째)은 수평 간선을, 짝수 번째 줄(2, 4, …번째)은 수평이 아닌 간선을 나타낸다. 각 줄은 공백 없이 문자 n, w, b로 이루어진 문자열이다. n은 원이 없는 간선, w는 흰색 원이 있는 간선, b는 검은색 원이 있는 간선을 뜻한다. 홀수 번째 줄은 정확히 W개의 문자로, 짝수 번째 줄은 정확히 2W+1개의 문자로 이루어진다.

입구에서 출구까지의 가장 짧은 경로의 길이를 정수 하나로 출력한다.