28104번 - 삼각형 모험

문제

포닉스는 $N \times M$ 크기의 격자에서 살고 있었다. 각 칸은 정사각형 모양이며, 격자의 각 칸에서는 상하좌우로 인접한 칸으로 자유롭게 이동할 수 있다.

그러던 어느 날, 사악한 마법사가 각 칸에 넘을 수 없는 대각선 형태의 벽을 설치했다! 격자의 각 칸은 직각이등변삼각형 모양의 두 영역으로 나뉘고 말았다. 포닉스는 상하좌우로는 이전과 같이 자유롭게 이동할 수 있지만, 대각선 형태의 벽을 넘어 이동할 수는 없다. 즉, 대각선이 아닌 변을 통해 인접한 삼각형으로만 이동할 수 있다. 더 이상 격자를 자유롭게 이동할 수 없게 된 포닉스는 자주 다니던 $Q$개의 경로에 대해 새로운 최소 이동 횟수를 계산하려 한다. $Q$개의 질문은 다음과 같이 주어진다.

• $x_1 \ y_1 \ t_1 \ x_2 \ y_2 \ t_2$: $(x_1, y_1, t_1)$에서 출발해 $(x_2, y_2, t_2)$로 도착하기 위한 이동 횟수의 최솟값을 구하여라.

$t = 0$은 해당 좌표의 위쪽 삼각형 영역을, $t = 1$은 해당 좌표의 아래쪽 삼각형 영역을 의미한다. 길을 잃은 포닉스를 위해 $Q$개의 경로에 대해 새로운 최소 이동 횟수를 계산해 보자!

입력

첫 번째 줄에 격자의 크기를 나타내는 정수 $N, M$과 질문의 개수 $Q$가 공백으로 구분되어 주어진다. (1ドル \leq N, M \leq 500; 1 \leq Q \leq 300\ 000$)

두 번째 줄부터 $N$개의 줄에 걸쳐 길이 $M$의 문자열이 주어진다. $i$번째 줄의 $j$번째 문자는 $i$번째 행 $j$번째 열에 위치한 칸에 나타난 대각선 벽의 형태를 의미한다. Z는 우상향 대각선을, N은 우하향 대각선을 의미한다.

$N+2$번째 줄부터 $Q$개의 줄에 걸쳐 $x_1 \ y_1 \ t_1 \ x_2 \ y_2 \ t_2$의 형태로 질문이 입력된다. (1ドル \leq x_1, x_2 \leq N; 1 \leq y_1, y_2 \leq M; 0 \leq t_1, t_2 \leq 1$)

주어지는 수는 모두 정수이다.

출력

각 질문에 대해 $(x_1, y_1, t_1)$에서 출발해 $(x_2, y_2, t_2)$로 도착하기 위한 이동 횟수의 최솟값을 한 줄에 하나씩 순서대로 출력한다. 해당하는 경로가 존재하지 않을 경우 -1을 출력한다.

제한

힌트

포닉스의 모험기는 후대에도 포스테키안들에게 전설로 전해지고 있다. 포스텍은 이를 기억하기 위해 학생회관 한편에 포닉스의 모험 당시의 격자를 재현해두었다고 한다.