| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 171 | 59 | 49 | 40.496% |
Albert는 혼자서도 할 수 있는 보드 게임을 즐겨한다. 이 게임을 플레이 하기 위해 우선 $R$ 행 $C$열 크기의 격자 보드 게임판을 준비한 후 임의의 칸에 벽을 설치한다. 이후, $N$개의 서로 다른 빈칸에 (즉, 벽이 없는 칸) 게임말을 하나씩 놓고, 마지막으로 남아있는 빈칸 중 한 곳을 골라 각 게임말이 도달해야하는 목적지를 정한다 - 목적지 칸의 위치를 $(r, c)$라 하자 ($r$행 $c$열). 편의상 게임말에는 1번부터 $N$번까지 번호가 붙어있다고 하고, $i$ 번째 말이 놓인 칸을 $(X_i, Y_i)$라 하자.
예를 들어 아래 그림의 좌측은 $R = C = 4$ 인 게임 보드판의 모습을 나타내고 'W' 로 표시된 칸은 벽을 나타낸다. 나머지 '.' 로 표시된 칸은 빈칸을 나타낸다. 편의상 이 문제에서 문자열 $A_i$는 $i$번째 행의 게임 보드판의 모습을 나타내는 길이가 $C$인 문자열이라 하면, 이 예제의 게임 보드판은 $A = [$".WW.", "..W.", ".WW.", "...."$]$ 로 나타낼 수 있다. 우측 그림은 이후 Albert가 총 3개의 게임말을 놓은 칸과 목적지 칸을 나타내는데, $X = [1, 1, 4],ドル $Y = [1, 4, 4$], 그리고 $(r, c) = (2, 2)$ 이다.
이 때 각 말이 목적지에 도달하려면 벽이 없는 빈칸을 통해 상/하/좌/우로 이동할 수 있는데, $i$번째 말이 목적지까지 이동해야하는 최소 거리를 $d_i$라 하자. 위 예제에서 $d_1 = 2$ (하 -> 우 로 이동하면 된다), $d_2 = 9,ドル 그리고 $d_3 = 6$ 임을 쉽게 알 수 있다. 모든 말이 이동해야하는 최소 거리의 총 합을 $D = \sum_{1 \le i \le N} d_i$ 라 하고, 이는 게임의 점수가 된다 - 이 예제의 게임 점수는 2ドル + 9 + 6 = 17$ 점이다.
이 놀이가 너무 심심하다고 느낀 Albet는 게임을 약간 변형해보기로 했다. 우선, 맨 처음의 보드 게임 상태를 유지한채로 벽을 하나 없애보기로 했다. 벽을 없애면 새로운 길이 생길 수 있으므로 게임의 점수는 같거나 낮아질텐데, 이 점수의 차이를 없어진 "벽의 가치"라 정의하자. 위 예제에서는 벽이 총 5칸 있으므로, 아래 그림 처럼 5가지 다른 방법으로 벽을 딱 하나 없앨 수 있다 - 벽이 없어진 칸은 알아보기 쉽도록 그림에서 'X'로 표시했지만 빈칸이므로 게임말이 지나갈 수 있다.
위 다섯가지의 새로운 게임 보드에서 점수를 구한 후 기존 게임의 점수 (앞서 구한 17점) 과의 차이를 구하면 없앤 벽의 가치가 된다. 왼쪽 부터 순서대로 이를 구해보면:
게임 보드의 상태가 주어졌을 때, 기존 게임의 점수 $D$를 구하고 모든 벽의 가치 총합도 구해보자.
입력 첫 줄에 테스트 케이스의 수 $T$ 가 주어진다.
각 테스트 케이스의 첫 줄에는 $R, C, N, r, c$가 공백으로 구분되어 주어진다. 다음 $N$줄에 걸쳐 각 줄에 한 쌍의 정수가 공백으로 구분되어 주어지는데 이는 순서대로 $i$번째 게임 말의 위치인 $X_i, Y_i$를 나타낸다. 다음 $R$줄에 걸쳐 각 줄에 길이가 $C$인 문자열이 공백없이 주어지는데 이는 순서대로 $i$번째 행의 보드 게임판을 나타내는 문자열 $A_i$ 이며, 벽이 있는 칸은 'W'가 주어지고 없는 칸은 '.'가 주어진다.
각 테스트 케이스의 정답인 한 쌍의 정수를 공백으로 구분하여 각 줄에 출력한다. 첫 정수는 기존 게임의 점수인 $D$를 출력하고 두 번째 정수는 모든 벽의 가치 총합을 나타낸다.
3 4 4 3 2 2 1 1 1 4 4 4 .WW. ..W. .WW. .... 5 7 3 2 4 2 1 4 3 3 7 .W..W.. .WW.WWW .W..W.. ....W.. ....... 5 7 3 2 4 2 1 4 3 3 7 .W..... .WW.WW. .W..W.. ....W.. ....W..
17 12 18 10 16 6
예제 1 - 본문에서 다루었다.
예제 2 - 입력으로 주어진 게임의 점수는 18점이다. 그리고 (1, 2), (3, 2), (3, 5), (4, 5)에 위치한 벽의 가치는 순서대로 2, 2, 4, 2 이고 나머지 벽의 가치는 0이다.
예제 3 - 입력으로 주어진 게임의 점수는 16점이다. (1, 2), (3, 2), (3, 5) 에 위치한 벽의 가치는 모두 2이고, 나머지 벽의 가치는 0이다.