곰돌이

곰돌이가 숲에서 꿀벌이 숨겨놓은 비밀 꿀단지를 발견했다. 단지에 가득 들어 있는 꿀을 먹으려는 순간 근처에 있는 벌 한 마리가 곰돌이를 발견하고 동료 벌들에게 신호를 보냈다. 곰돌이는 곧 수많은 벌들이 벌집을 출발해 자신을 공격할 것을 직감하고, 벌들의 공격을 피해 자신의 집으로 돌아가야 한다고 생각했다. 곰돌이는 꿀단지가 있는 위치에 가능한 한 오래 남아 꿀을 먹은 후 꿀단지를 떠나 안전하게 집에 도착하고 싶다. 곰돌이가 가장 늦게 떠나도 되는 시간을 계산하라.

곰돌이와 벌들이 있는 숲은 단위 정사각형들의 칸으로 구성된 N 행과 N 개의 열의 격자 판이다. 격자 판의 각 정사각형 칸에는 나무 한 그루가 있거나, 풀밭이거나, 벌집이거나, 곰돌이 집이다. 곰돌이는 한 번에 한 칸씩만 동, 서, 남, 북으로 인접한 칸들 중 하나로 이동할 수 있다. (대각선 방향으로 인접한 칸으로는 이동할 수 없다.) 그리고 곰돌이는 나무나 벌집이 있는 칸으로는 이동할 수 없고 오직 풀밭이 있는 인접한 칸으로만 이동할 수 있다. 곰돌이는 1분에 최대 S칸을 움직일 수 있다.

벌이 곰돌이를 최초로 발견하고 다른 벌들에게 신호를 보내는 순간에 곰돌이는 꿀단지가 있는 풀밭 간에 있다. 벌집이 있는 칸에는 무수히 많은 벌들이 있다고 가정한다. (벌집이 있는 칸은 하나 이상일 수 있음에 유의하자.) 이 숲의 시계는 분 단위로 움직인다. 매 분마다 다음과 같은 이벤트가 발생한다:

• 만약 곰돌이가 현재 꿀을 먹고 있다면, 곰돌이는 자신이 계속 꿀을 먹을지 아니면 꿀단지를 떠나 집으로 갈지를 결정해야 한다. 만약 꿀을 계속 먹겠다고 결정하면 1 분 동안은 움직일 수 없다. 반대로 가겠다고 결정하면, 즉각 떠나야 하며 1 분에 최대 S 칸을 이동할 수 있다. 떠나게 되면 꿀단지는 가지고 갈 수 없기 때문에, 떠난 후에는 꿀을 다시 먹을 순 없다. 곰돌이가 이동할 수 있는 칸은 위에서 설명한 것처럼 동, 서, 남, 북으로 인접한 풀밭이 있는 칸이다.
• 곰돌이가 1분 동안 꿀을 먹거나 움직인 후, 1 분이 완료되는 순간 벌들은 자신들이 있는 칸에서 인접한 모든 칸으로 퍼져 나간다. 이때, 벌들이 이동할 수 있는 칸은 동, 서, 남, 북 중 한 방향으로 인접한 칸이어야 하며 그 중 풀밭이 있는 칸이어야 한다. (대각선 방향으로 이웃한 칸으로는 이동이 불가능하다.) 결국, 벌들이 있는 각 칸에서 그 칸에 인접한 모든 풀밭 칸으로 벌들이 동시에 한 칸씩 퍼져 나가게 된다. 주의할 점은 어떤 칸에 벌들이 있게 되면 그 칸에는 영원히 벌들이 존재하게 된다는 것이다. 즉, 시간이 흐를수록 벌들이 숲의 여러 칸으로 확산되어 벌들이 있는 칸이 계속 늘어나게 된다.

다시 한번 벌들의 움직임을 설명하면 다음과 같다 : 벌 한마리가 신호를 보내는 순간에는 벌집이 있는 칸들에만 벌들이 있게 된다. 1 분이 완료되는 순간에는 벌들은 벌집이 있는 칸들과 그 칸들에 인접한 모든 풀밭 칸을 차지하게 된다. 2 분이 완료되는 순간에는 벌집이 있는 칸 모두와 벌집에 인접한 모든 풀밭 칸들과 그 풀밭 칸들에 인접한 모든 풀밭 칸들을 차지하게 된다. 충분히 긴 시간이 지나게 되면, 벌집에서 출발하여 도달 가능한 모든 풀밭 칸을 벌들이 차지하게 될 것이다.

곰돌이와 벌들은 숲 밖으로 나갈 수 없으며, 곰돌이가 꿀을 먹는 시간은 정수 값이다.

벌들이 차지한 칸에 곰돌이가 함께 있게 되는 순간 곰돌이는 벌들에 의해 잡히게 된다.

숲의 지도가 주어졌을 때, 곰돌이가 집에 도착하기 전에 벌들에게 잡히지 않으면서 꿀단지가 있는 위치에서 계속해서 꿀을 먹을 수 있는 가장 긴 시간을 계산하는 프로그램을 작성하라.

반드시 표준 입력으로부터 다음의 데이터를 읽어야 한다 :

• 첫째 줄은 두 정수 N과 S가 공백을 사이에 두고 주어진다.

• 다음 N개의 줄에는 지도 정보가 주어진다. 각 줄에는 N개의 문자가 공백 없이 주어지는 데, 각 문자는 한 칸의 상태를 다음과 같이 나타낸다 :

  • T는 나무가 있는 칸을 나타낸다.
  • G는 풀밭이 있는 칸을 나타낸다.
  • M은 곰돌이의 최초 위치(꿀단지가 있는 칸)이고 동시에 풀밭 칸이기도 하다.
  • D는 곰돌이의 집을 나타내는데, 곰돌이는 들어갈 수 있지만 벌들은 들어갈 수 없다.
  • H는 벌집이 있는 칸을 나타낸다.

주의사항 : 지도는 항상 정확히 하나의 M, 정확히 하나의 D 그리고 하나 이상의 H를 포함하고 있다. 또한 곰돌이의 최초 위치부터 곰돌이의 집을 연결하는 G 칸들의 경로가 하나 이상 반드시 존재하며, 적어도 하나 이상의 벌집과 꿀단지(곰돌이의 최초 위치)를 연결하는 풀밭 칸의 경로도 하나 이상 존재한다. 곰돌이의 최초 위치에 인접한 칸에 곰돌이의 집이나 벌집이 위치할 수도 있다. 마지막으로 벌들은 곰돌이의 집을 통과할 수 없다.

• 1 <= N <= 800 지도의 크기 (한 변을 이루는 칸의 수)
• 1 <= S <= 1,000 곰돌이가 1 분 동안 움직일 수 있는 칸의 최대 수

출력은 반드시 표준 출력으로 해야 하며, 한 줄에 하나의 정수를 출력한다. 그 정수는 곰돌이가 최초 위치에서 안전하게 집에 도달하기 위해, 꿀을 계속해서 먹을 수 있는 가장 긴 시간(분)이다.

만약 곰돌이가 벌들에게 잡히지 않고 집에 도달하는 것이 불가능하다면 표준 출력으로 -1을 출력해야 한다.

곰돌이가 1 분 동안 꿀을 먹은 후, 오른쪽 방향으로 일직선 최단 경로를 통해 다음 2분에 걸쳐 안전하게 집에 도착할 수 있다. 따라서 곰돌이가 꿀을 먹을 수 있는 최장 시간은 1분이 되어 출력 값은 1이다.