30894번 - 유령의 집 탈출하기

문제

오랜만에 놀이공원에 놀러 가기로 한 석준이는 친구들과 다음과 같은 대화를 나누었습니다.

• 친구A: 유령의 집은 너무 무서울 것 같지 않아? 그냥 롤러코스터 타러 가자...
• 석준: 에이~ 유령의 집이 뭐가 무서워? 줄도 없는데 빨리 들어갔다 나오자!
• 친구B: 그래? 그러면 네가 앞장서서 가면 되겠다. 잘 부탁해~
• 석준: ....

사실 석준이는 누구보다도 유령을 무서워하지만, 이미 허세를 부려버려 돌이킬 방법이 없었습니다.

세로 $N$칸, 가로 $M$칸 크기의 유령의 집은 다음과 같이 구성되어 있습니다.

• 빈칸(.): 석준이가 움직일 수 있는 공간을 의미합니다.
• 벽(#): 석준이가 움직일 수 없는 공간을 의미합니다.
• 유령(0, 1, 2, 3): 각 숫자는 유령이 바라보는 초기 방향을 의미합니다. (0 : 오른쪽, 1 : 아래, 2 : 왼쪽, 3 : 위)

어떤 유령이 바라보는 방향에 벽이나 다른 유령이 존재하는 경우, 시야가 가로막혀 그 뒤의 공간은 볼 수 없습니다. 단, 유령의 시야가 가로막히지 않았고 바라보는 방향에 석준이가 있다면, 유령은 거리에 상관없이 석준이를 발견할 수 있습니다. 각 유령은 매초 시계 방향으로 90ドル$°씩 회전하며, 회전하는 동안에는 석준이를 볼 수 없습니다.

석준이는 매초 상하좌우로 인접한 빈칸으로 이동하거나 제자리에 머무를 수 있습니다.

놀이공원 아르바이트 경험이 있던 석준이는 유령의 위치와 지도를 모두 알고 있었고, 어떤 유령에게도 발견되지 않고 최대한 빨리 탈출할 계획을 세우려 합니다.

이미 긴장감에 휩싸여 머리가 새하얘진 석준이를 위해, 여러분이 그 방법을 대신 찾아주세요.

입력

첫째 줄에 유령의 집의 크기 $N, M$이 주어집니다.$(2≤N,M≤200)$

둘째 줄에 유령의 집의 입구 좌표 $S_x, S_y,ドル 출구 좌표 $E_x, E_y$가 주어집니다.$(1≤S_x, E_x≤N, 1≤S_y, E_y≤M)$

좌표 $(x, y)$는 위에서부터 $x$번째 칸, 왼쪽에서부터 $y$번째 칸을 의미합니다.

입구와 출구는 빈칸이며, 두 좌표는 서로 다릅니다. 또한, 시각 0ドル$에 유령이 입구를 바라보고 있지 않음이 보장됩니다.

다음 $N$개의 줄에 걸쳐서 유령의 집의 상태가 주어집니다.

출력

유령의 집을 탈출하는 데 걸리는 최소 시간을 출력합니다.

만약 유령에게 발견되지 않고 탈출할 방법이 없다면, GG를 출력합니다.

제한

힌트