시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2.5 초 (추가 시간 없음) 1024 MB 78 14 10 18.519%

문제

N × N 격자의 각 칸에 양파가 하나씩 심어져 있다. 각각의 양파에는 세균이 한 마리씩 살고 있는데, 이 세균들은 자주 모임을 연다. 이 격자에서 좌표 (r, c)는 r번째 행의 c번째 열에 있는 칸을 뜻한다. 각 세균에게는 두 가지 이동 방법이 있는데, 착한 말과 나쁜 말이다. 나쁜 말을 한 번 하면 a의 에너지가 소모된다. 착한 말을 하려면 지금 세균이 있는 칸이 착한 칸이어야 하며, b의 에너지가 소모된다. 현재 위치가 (r, c)라고 할 때 나쁜 말을 하면 화난 양파가 세균을 옆의 양파로 밀어내서 |r' - r|+|c' - c| = 1을 만족하는 (r', c')로 이동할 수 있으며, 착한 말을 하면 양파가 순간적으로 성장해서 세균을 높이 띄워주어 max(|r' - r|, |c' - c|) ≤ D를 만족하는 (r', c')로 이동할 수 있다. 당연히 격자 밖으로 나가는 것은 불가능하다.

세균들이 계획한 i일의 모임 일정은 (Ri, Ci)에서 열리고, 이 날 태양 빛의 세기에 따라 a = Ai, b = Bi가 정해진다. 세균들이 각자 최소의 에너지를 사용하여 이동한다고 할 때, 모든 칸의 세균들이 모이기 위해 세균들이 사용해야 하는 총 에너지 합을 구해주자. 단, 양파는 한 번에 세균 하나씩만 이동시킬 수 있다고 한다. 모든 세균들은 모임이 끝난 뒤 자기가 사는 양파로 돌아가는데, 이 때는 에너지를 소모하지 않는다.

입력

1번째 줄에 격자의 크기 N, 착한 말을 했을 때의 이동 범위 D, 모임 날짜의 수 Q가 공백으로 구분되어 주어진다.

i + 1번째 줄에는 길이 N의 문자열로 격자의 i번째 행의 상태가 주어진다. j번째 문자가 '.'일 경우 (i, j)는 나쁜 칸이며, '#'일 경우 착한 칸이다. (1 ≤ i, j ≤ N)

i + N + 1번째 줄에는 i일의 모임 일정에 대한 정보 Ri, Ci, Ai, Bi가 공백으로 구분되어 주어진다. (1 ≤ i ≤ Q)

출력

i번째 줄에 i일의 모임 일정에서 세균들이 사용해야 하는 총 에너지 합을 출력한다. (1 ≤ i ≤ Q)

제한

  • 1 ≤ D ≤ N ≤ 500
  • 1 ≤ Q ≤ 5
  • 1 ≤ Ri, Ci ≤ N (1 ≤ i ≤ Q)
  • 1 ≤ Ai, Bi ≤ 109 (1 ≤ i ≤ Q)

예제 입력 1

3 1 2
#..
...
...
1 1 10 1
2 2 1 1

예제 출력 1

180
11

예제 입력 2

8 2 4
........
........
....#...
........
.......#
..#..#..
........
........
6 1 3 1
8 2 100 1
4 3 1 3
2 4 1 100

예제 출력 2

605
17798
263
304

출처

Contest > IDTcup > 제 2회 IDTcup C번