2782번

수정 전

시간 제한 메모리 제한
1 초 128 MB

문제

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

힌트

수정 후

시간 제한 메모리 제한
10 초 128 MB

문제

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

힌트