문제
곰돌이 푸는 꿀벌들이 숨겨놓은 꿀이 가득 찬 꿀통을 발견하였다!
푸는 매우 행복하게 꿀을 먹고 있었는데, 갑자기 벌들이 윙윙거리는 소리가 들려왔다.
푸는 꿀벌 떼가 자신을 잡으러 올 것을 예감하고 빨리 자신의 집으로 돌아오려고 한다.
하지만 꿀이 너무 맛있기 때문에 푸는 꿀통에서 최대한 오래 있다가 집으로 가려고 한다.
푸가 살고 있는 숲은 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을 출력한다.
예제1
7 3
TTTTTTT
TGGGGGT
TGGGGGT
MGGGGGD
TGGGGGT
TGGGGGT
THHHHHT
1