IOI 2009 day2 2- 곰돌이 푸 (Mecho) > 문제은행 : 정보올림피아드&알고리즘




2683 : 곰돌이 푸 (Mecho)

제한시간
2000 ms   
메모리제한
64 MB   
해결횟수
18 회   
시도횟수
105 회   

문제

곰돌이 푸는 꿀벌들이 숨겨놓은 꿀이 가득 찬 꿀통을 발견하였다! 

푸는 매우 행복하게 꿀을 먹고 있었는데, 갑자기 벌들이 윙윙거리는 소리가 들려왔다. 

푸는 꿀벌 떼가 자신을 잡으러 올 것을 예감하고 빨리 자신의 집으로 돌아오려고 한다. 

하지만 꿀이 너무 맛있기 때문에 푸는 꿀통에서 최대한 오래 있다가 집으로 가려고 한다.


푸가 살고 있는 숲은 N x N 크기의 격자 모양으로 되어 있다. 

각 격자에는 나무 혹은 풀밭이 있거나, 벌집, 꿀통, 또는 푸의 집이 있다. 

벌집은 여러 개 있을 수 있지만 푸의 집은 한 개뿐이다. 

푸가 처음 벌들을 발견한 순간에는 푸는 꿀통이 위치한 격자 위에 있고, 벌들은 오직 벌집이 위치한 격자 위에만 있다.

매 분마다, 다음 일들이 나열된 순서대로 일어난다.


- 푸가 여전히 꿀을 먹고 있다면, 그는 꿀을 계속 먹을 지, 아니면 자신의 집으로 갈 지를 결정한다.

  만약 그가 꿀을 계속 먹는다면, 1분 동안 그는 가만히 있는다. 

  그렇지 않으면 그는 상하좌우 방향으로 최대 S걸음만큼 움직인다. 

  푸는 꿀을 가져갈 수 없으며, 따라서 한 번 꿀통을 떠나면 더 이상 꿀을 먹지 못한다.

- 푸가 꿀을 먹거나 움직인 후에는 벌들이 상하좌우로 한 칸씩 퍼진다. 

  한 번 벌들이 퍼진 곳에는 계속 벌이 있다. 

  즉, 벌들은 처음에는 벌집에만 있고, 1분 후에는 벌집과 인접한 칸에도 벌이 있고, ….

  푸는 풀밭, 꿀통, 집이 있는 곳으로만 다닐 수 있고, 벌들은 풀밭, 꿀통 쪽으로만 퍼진다. 

  푸와 벌들은 숲 밖으로 나가지 않는다.

  푸가 있는 격자가 벌들이 이미 퍼진 곳이라면, 푸는 벌들에게 잡힌다. 


푸가 꿀을 최대 얼마동안 먹을 수 있는지 구하는 프로그램을 작성하여라.



입력형식

첫 번째 줄에는 N, S가 주어진다.
두 번째 줄부터 N개의 줄에는 숲의 정보가 공백 없이 주어진다. 'T', 'G', 'M', 'D', 'H'는 각각 나무, 풀밭, 꿀통, 푸의 집, 벌집을 나타낸다. 'M', 'D'는 정확히 한 번 주어지며, 'H'는 한 번 이상 주어진다. 또, 꿀통에서 푸의 집까지 갈 수 있는 경로가 존재하며, 꿀통에서 한 개 이상의 벌집까지 갈 수 있는 경로 역시 존재한다.

<제약조건>
1 ≤ N ≤ 800 (N : 숲의 크기)
1 ≤ S ≤ 2,000 (S : 푸가 1분 동안 걸을 수 있는 걸음의 수)

전체 데이터의 40%는 N ≤ 60이다.


출력형식

푸가 벌에게 잡히지 않고 집까지 갈 때, 푸가 꿀을 먹을 수 있는 최대 시간을 출력한다.
만약 푸가 벌에게 잡히지 않고 집까지 갈 수 없으면 -1을 출력한다.

 


입력 예

7 3
TTTTTTT
TGGGGGT
TGGGGGT
MGGGGGD
TGGGGGT
TGGGGGT
THHHHHT

출력 예

1

Hint!

푸는 1분 동안 꿀을 먹은 후, 오른쪽으로 계속 걸으면 집까지 안전하게 갈 수 있다.




경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP