로맨틱 왕
시간 제한10초메모리 제한128 MB
격자에서 선물 개수가 많아질수록 이동 속도가 느려지는 조건에서 주어진 시간 안에 왕비에게 배달 가능한 최대 선물 수를 구하는 문제입니다.
문제
왕비를 무척 사랑하는 왕이 있었다. 어느 날 왕은 왕비를 기쁘게 해 주려고 깜짝 파티를 준비했지만, 파티가 시작되기 몇 시간 전에 왕비에게 줄 선물을 준비하지 않았다는 사실을 깨달았다.
다행히 왕과 왕비가 사는 도시 주변에는 선물 나무가 자란다. 왕은 가능한 한 많은 선물을 가져가고 싶지만, 평소 운동을 전혀 하지 않아 들고 있는 선물이 많을수록 이동 속도가 느려진다.
왕은 K에서 출발해 주어진 시간 안에 왕비가 있는 성 Q에 도착해야 한다. 왕은 선물을 들고 있지 않으면 한 칸을 이동하는 데 1시간이 걸린다. 선물을 q개 들고 있으면 한 칸을 이동하는 데 q + 1시간이 걸린다. 각 선물 나무 G에서는 선물 하나를 얻을 수 있다. 선물을 더 가지러 가는 동안 왕비가 있는 칸을 지나쳐도 되며, 마지막에 그 칸에 도착하면 된다.
왕이 왕비에게 가져다줄 수 있는 선물의 최대 개수를 구하라.
입력
첫째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스마다 한 줄에 도시 지도의 세로 크기, 가로 크기, 주어진 시간이 주어진다. 이어서 세로 크기개의 줄에 도시 지도가 주어진다.
지도에 사용되는 문자는 다음과 같다.
Q: 왕비가 있는 성K: 왕의 현재 위치G: 선물 나무.: 길#: 지나갈 수 없는 칸
도시 지도의 세로 크기와 가로 크기는 각각 1 이상 50 이하이다. 한 도시에 있는 선물 나무는 0개 이상 16개 이하이다. 입력은 항상 왕이 왕비가 있는 곳에 도착할 수 있는 경우만 주어진다.
출력
각 테스트 케이스마다 왕이 왕비에게 가져다줄 수 있는 선물의 최대 개수를 출력한다.