문제
어느덧 여름이 찾아왔다!
더위에 약한 석표는 땡볕 아래서는 물 없이는 단 1초도 버티지 못한다.
석표가 사는 마을은 H * W의 격자로 나타낼 수 있다.
격자의 각 칸은 벽, 건물, 빈 곳의 3가지 중 하나이다.
건물은 총 한칸에 하나씩 총 N개가 있으며 각각 1~N 사이의 번호가 붙어 있다.
i번 건물은 A_i행 B_i열에 위치한다.
석표는 건물 사이를 이동하고 싶어한다.
석표는 1분에 1칸씩 상하좌우에 인접한 칸으로 이동할 수 있다.
이때, 벽이 있는 위치로는 이동할 수 없다.
석표는 더위를 극복하기 위해 큰 물병을 들고 다닌다.
건물이 아닌 빈 공간을 지날 때는 한 칸에 1컵씩 물을 마셔야만 한다.
건물이 있는 위치를 지날 때는 물을 마시지 않으며 정수기에서 물병을 가득 채울 수 있다.
석표는 Q개의 상황에 대해 생각한다.
i번째 상황에서는 석표가 U_i번 건물에서 V_i번 건물로 이동하는 상황을 생각한다.
석표는 물을 마셔야 하지만 동시에 물통이 너무 크면 불편하다고 생각한다.
물을 마시며 이동할 수만 있다면 이동에 걸리는 시간이나 다른 요인은 중요하지 않다.
각 상황에 대해 석표가 원하는 대로 이동하기 위해서 필요한 최소의 물통은 몇 컵 분량인지 구하자.
입력
첫 줄에 H, W, N, Q가 차례로 주어진다.
그 뒤 H줄에 걸쳐 각 칸의 벽에 대한 정보가 주어진다.
#는 벽이 있음을 의미하고 .은 벽이 없음을 의미한다.
다음 N줄에 걸쳐 i번째 줄에 A_i, B_i가 주어진다.
다음 Q줄에 걸쳐 i번째 줄에 U_i, V_i가 주어진다.
1 <= H, W <= 2,000
2 <= N <= 200,000
1 <= Q <= 200,000
1 <= A_i <= H
1 <= B_i <= W
(A_i, B_i) != (A_j, B_j) (1 <= i < j <= N)
1 <= U_i < V_i <= N
Q=1 인 경우를 해결하면 30%의 점수를 받을 수 있음이 보장된다.
출력
Q줄에 걸쳐 각 질문에 대한 답을 한 줄에 하나씩 출력하라.
이동이 불가능하다면 질문에 대한 답은 -1이다.
예제 #1
5 5 4 4
.....
..##.
.#...
..#..
.....
1 1
4 2
3 3
2 5
1 2
2 4
1 3
3 4
3
4
4
2
예제 #2
5 5 3 2
...#.
..#..
#....
.##..
...#.
1 3
5 2
1 5
1 2
1 3
-1
7
로그인해야 코드를 작성할 수 있어요.