← 목록으로

청소기 로봇

가구가 배치된 방에 청소기 로봇이 있다. 방은 세로 N칸, 가로 M칸인 2차원 격자칸으로 표현한다. 각 칸은 로봇이 갈 수 있는 칸과 가구가 배치되어 갈 수 없는 칸들로 구별된다고 한다. 격자의 가장 바깥쪽 한 줄은 모두 갈 수 없는 칸들이라고 가정한다. 또, 갈 수 없는 칸들이 상하좌우로 인접한 것은 연결된 것이라고 했을 때, 모든 갈 수 없는 칸들은 연결되어 있다.

Q개의 쿼리가 주어진다. 각 쿼리는 격자칸의 위치 두 개이다. 각 위치는 (행번호, 열번호)의 좌표로 주어진다. 행 번호는 위에서부터 1로 시작하여 N까지, 열 번호는 왼쪽에서부터 1로 시작하여 M까지 번호가 매겨진다. 각 쿼리에 대한 대답은 주어진 위치들을 연결하는 가장 짧은 길의 길이이다. 로봇은 상하좌우로 인접한 칸으로만 움직일 수 있다. 길의 길이는 로봇이 인접한 칸으로 이동한 횟수로 표현한다.

주어진 가구 배치에 대해서 쿼리들에 대한 대답을 계산하는 프로그램을 작성하시오.

입력 형식

첫째 줄에 그려지는 세로 칸 수 N, 가로 칸 수 M, 쿼리의 개수 Q가 공백으로 구분되어 주어진다. (3 ≤ N, M ≤ 1,000, 1 ≤ Q ≤ 200,000)

다음 N개의 줄에는 방의 배치를 나타내는 M개의 글자가 각각 주어진다. 각 글자는 '.'인 경우 로봇이 갈 수 있는 칸, '#'인 경우 로봇이 갈 수 없는 칸이다.

다음 Q개의 줄에 쿼리가 하나씩 주어진다. 각 쿼리는 R1, C1, R2, C2 네 개의 정수가 공백으로 구분되어 주어진다. 이는 쿼리의 두 위치의 좌표가 (R1, C1)와 (R2, C2)임을 의미한다. 또한 좌표는 로봇이 갈 수 있는 칸들에 대해서만 주어진다.

출력 형식

각 쿼리에 대해서 한 줄에 정수를 하나 출력한다. 두 위치 간을 이동하는 것이 가능한 경우 가장 짧은 길의 길이를 출력한다. 이동이 불가능한 경우 -1을 출력한다.

입력 예제

6 6 2
######
#....#
#.##.#
#.#.##
#.#.##
######
5 2 3 5
5 2 5 4

출력 예제

7
-1

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

###########
####..#####
##.......##
###.....###
#####.....#
#####.#####
#.....#####
#####.....#
#####.#####
##.....####
###......##
###########

해설