시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
10 초 128 MB 61 7 6 12.500%

문제

옛날에 왕비를 매우 사랑하는 왕이 살았다. 하루는 왕비를 기쁘게 해주고 싶은 왕은 왕비를 위해 깜짝 파티를 해주기로 했다. 왕비 몰래 파티 준비를 하던 왕은 파티가 시작되기 몇 시간을 앞두고 자신이 왕비에게 줄 선물을 깜빡 했다는 사실을 깨달았다. 왕은 절망했지만 다행히 왕과 왕비가 사는 주변에는 선물 나무라는 것이 자라서 선물을 구할 수 있다는 사실이 떠올랐다. 왕비를 사랑하는 왕은 선물을 가능한 많이 따다 주고 싶었지만, 왕은 운동을 전혀 하지 않는 사람이라 선물을 많이 딸 수록 발걸음이 느려진다. 주어진 왕이 왕비에게 줄 수 있는 최대 선물의 개수를 알아 보자.(왕은 시작한 곳에서 왕비가 있는 곳까지 주어진 시간 이내 반드시 가야 한다. 또한 왕은 기본적으로 1시간에 한 칸씩 이동하는데, 선물 q개를 가지고는 한 칸에 (q+1)시간이 걸린다. 선물을 가지러 갈 때 왕비를 지나쳐도 괜찮다.)

입력

첫째 줄에 test case T가 주어진다. 둘째 줄부터 도시 지도의 세로, 가로 크기와 주어진 시간이 주어진다. 그 다음 줄에는 도시의 지도가 주어진다. Q는 왕비가 있는 성이고, K은 지금 왕이 있는 위치이다. G는 선물 나무의 위치이고 .은 그냥 길, #은 가지 못하는 길이다.  이 도시의 크기는 가로, 세로 최소 1부터 최대 50까지 가능하다. 선물 나무 G는 한 도시에 0~16개까지 자랄 수 있다. 항상 왕비가 있는 곳으로 갈 수 있는 경우만 입력으로 주어진다.

출력

왕이 가지고 올 수 있는 최대의 선물 개수를 출력한다.

예제 입력

2
3 7 6
#######
#K.G.Q#
#######
3 7 4
#######
#K.G.Q#
#######

예제 출력

1
0

힌트

출처

  • 문제의 오타를 찾은 사람: myungwoo