레이팅 미적용곰 메초는 \(N \times N\) 격자 위에 있다. 칸은 풀밭 G, 나무 T(지나갈 수 없음), 벌집 H, 메초의 시작 위치 M, 그리고 그의 집 동굴 D로 이루어져 있다. 벌들은 모든 벌집에서 풀밭을 통해 퍼지며, 매 분마다 정확히 한 칸씩(4방향으로) 전진한다. 벌들은 동굴 D, 나무, 벌집에는 절대 들어가지 않는다. 메초는 풀밭을 지나(그리고 D로) 1분에 최대 \(S\)걸음 걸을 수 있다.
메초는 먼저 M에서 정수 분 동안 꿀을 먹으며, 그동안 벌들은 계속 퍼진다. 그 후 집으로 걸어간다. 시간 규칙: \(t\)분 동안 먹었다면, \(s\)걸음을 걸은 뒤의 현재 분은 \(t + \lfloor s / S \rfloor\)이다. 메초는 벌들이 그 분보다 엄격히 늦게 도달하는 칸만 차지할 수 있다.
메초가 여전히 동굴에 안전하게 도달할 수 있는 최대 \(t\)를 출력하시오. 즉시 떠나도 도달할 수 없으면 -1을 출력한다.
참고. 이 문제는 IOI의 함수 구현형 문제를 표준 입출력 문제로 각색한 것이다. 테스트 데이터는 RiseOJ에서 생성한 것으로(독립적인 브루트포스와 교차 검증됨), 공식 IOI 데이터가 아니다.
인터랙션 / 입출력 프로토콜
입력. 첫째 줄: \(N\)과 \(S\). 다음 \(N\)개의 줄에는 각각 격자를 나타내는, GTHMD의 문자 \(N\)개로 이루어진 문자열이 주어진다.
출력. 최대 꿀 먹기 시간, 또는 -1을 나타내는 정수 하나를 출력한다.
예제.
MGGG
GGGG
GGGG
HGGD
S=1일 때: 답은 메초가 벌들보다 앞서 D에 도달할 수 있으면서 기다릴 수 있는 최대 분 수이다.
- \(1 \le N \le 800\)
- \(1 \le S \le 1000\)
M과D는 정확히 하나씩,H는 적어도 하나 있다.
첫째 줄: \(N\)과 \(S\). 다음 \(N\)개의 줄에는 각각 격자를 나타내는, GTHMD의 문자 \(N\)개로 이루어진 문자열이 주어진다.
최대 꿀 먹기 시간, 또는 -1을 나타내는 정수 하나를 출력한다.