레이팅 미적용August 8 – 15, Plovdiv, Bulgaria
Contest Day 2 - Mecho
English 1.1
메초 (MECHO)
곰 메초는 작은 보물을 발견했다 – 꿀이 가득한 벌들의 비밀 꿀단지! 새로 찾은 보물을 행복하게 먹고 있었는데, 갑자기 벌 한 마리가 그를 발견하고 벌 경보를 울렸다. 메초는 바로 이 순간 벌 떼가 벌집에서 나와 자신을 잡으려고 퍼지기 시작할 것을 안다. 꿀단지를 떠나 빨리 집에 가야 한다는 것을 알지만, 꿀이 너무 달콤해서 메초는 너무 일찍 떠나고 싶지 않다. 메초가 떠날 수 있는 가장 늦은 시점을 결정하도록 도와주시오.
메초의 숲은 남북 및 동서 방향과 변이 평행한 N × N 단위 칸의 정사각 격자로 표현된다. 각 칸은 나무, 풀밭, 벌집, 또는 메초의 집 중 하나이다. 두 칸 중 하나가 다른 하나의 바로 북, 남, 동, 서에 있으면(대각선은 제외) 두 칸은 인접하다고 한다. 메초는 서투른 곰이라 한 걸음을 옮길 때마다 인접한 칸으로만 이동해야 한다. 메초는 풀밭 위로만 걸을 수 있고 나무나 벌집을 통과할 수 없으며, 1분에 최대 S걸음을 걸을 수 있다.
벌 경보가 울리는 순간, 메초는 꿀단지가 있는 풀밭 칸에 있고, 벌들은 벌집이 있는 모든 칸에 있다(숲에 벌집이 여러 개 있을 수 있다). 이 시점부터 매 분마다 다음 사건들이 다음 순서로 일어난다:
• 메초가 아직 꿀을 먹고 있다면, 계속 먹을지 떠날지 결정한다. 계속 먹는다면 그 1분 동안 움직이지 않는다. 그렇지 않으면 즉시 떠나서 위에 설명한 대로 숲을 최대 S걸음 이동한다. 메초는 꿀을 가지고 갈 수 없으므로, 일단 움직이면 다시 꿀을 먹을 수 없다.
• 메초가 그 1분 동안 먹거나 이동하는 것을 마친 후, 벌들은 격자에서 한 칸 더 퍼지며, 풀밭 칸으로만 이동한다. 구체적으로, 벌 떼는 이미 벌이 있는 칸에 인접한 모든 풀밭 칸으로 퍼진다. 또한 일단 벌이 있는 칸에는 항상 벌이 있다(즉, 벌 떼는 이동하는 것이 아니라 커진다).
다시 말해, 벌들은 다음과 같이 퍼진다: 벌 경보가 울릴 때 벌들은 벌집이 있는 칸만 차지한다. 첫 1분이 끝나면 벌집에 인접한 모든 풀밭 칸을(그리고 여전히 벌집 자체도) 차지한다. 두 번째 1분이 끝나면 추가로 벌집에 인접한 풀밭 칸에 인접한 모든 풀밭 칸을 차지하며, 이하 같다. 시간이 충분히 지나면 벌들은 결국 도달 가능한 숲의 모든 풀밭 칸을 동시에 차지하게 된다.
메초도 벌들도 숲 밖으로 나갈 수 없다. 또한 위 규칙에 따르면 메초는 항상 정수 분 동안 꿀을 먹게 됨에 유의하라.
어느 시점에든 메초가 벌이 차지한 칸에 있게 되면 벌들이 메초를 잡는다.
August 8 – 15, Plovdiv, Bulgaria
Contest Day 2 - Mecho
English 1.1
TASK
숲의 지도가 주어졌을 때, 메초가 벌에게 잡히기 전에 집에 도착할 수 있으면서 처음 위치에서 꿀을 계속 먹을 수 있는 최대 분 수를 구하는 프로그램을 작성하시오.
EXAMPLES
Sample Input
Sample Output
7 3
TTTTTTT
TGGGGGT
TGGGGGT
MGGGGGD
TGGGGGT
TGGGGGT
THHHHHT
1
1분 동안 꿀을 먹은 뒤, 메초는 곧바로 오른쪽으로 최단 경로를 택하면 2분 뒤에 벌들로부터 안전하게 집에 도착한다.
Sample Input
Sample Output
7 3
TTTTTTT
TGGGGGT
TGGGGGT
MGGGGGD
TGGGGGT
TGGGGGT
TGHHGGT
2
2분 동안 꿀을 먹은 뒤, 메초는 세 번째 분에 →↑→ 걸음을, 네 번째 분에 →→→ 걸음을, 다섯 번째 분에 ↓→ 걸음을 걸으면 된다.
\(1 \le N \le 800\)
지도의 크기(한 변의 길이)
\(1 \le S \le 1,000\)
메초가 1분에 걸을 수 있는 최대 걸음 수
프로그램은 표준 입력에서 다음 데이터를 읽어야 한다:
• 첫 줄에는 정수 N과 S가 공백으로 구분되어 주어진다.
• 다음 N개의 줄은 숲의 지도를 나타낸다. 각 줄에는 N개의 문자가 있으며, 각 문자는 격자의 단위 칸 하나를 나타낸다. 가능한 문자와 그 의미는 다음과 같다:
T 는 나무를 나타낸다
G 는 풀밭 칸을 나타낸다
M 은 메초의 처음 위치이자 꿀단지의 위치를 나타내며, 이 칸도 풀밭 칸이다
D 는 메초의 집 위치를 나타내며, 메초는 들어갈 수 있지만 벌들은 들어갈 수 없다.
H 는 벌집의 위치를 나타낸다
NOTE: 지도에는 정확히 하나의 M, 정확히 하나의 D, 그리고 적어도 하나의 H가 있음이 보장된다. 또한 메초와 집을 잇는 인접한 G 문자들의 수열이 존재하고, 적어도 하나의 벌집과 꿀단지(즉, 메초의 처음 위치)를 잇는 인접한 G 문자들의 수열도 존재함이 보장된다. 메초의 집이나 벌집이 메초의 처음 위치에 인접한 경우 이 수열의 길이는 0일 수도 있다. 또한 벌들은 메초의 집을 통과하거나 그 위로 날 수 없음에 유의하라. 벌들에게 집은 나무와 같다.
프로그램은 표준 출력에 정수 하나가 있는 한 줄을 출력해야 한다: 메초가 안전하게 집에 도착할 수 있으면서 처음 위치에서 꿀을 계속 먹을 수 있는 최대 분 수.
메초가 벌에게 잡히기 전에 집에 도착하는 것이 아예 불가능하다면, 프로그램은 표준 출력에 대신 -1을 출력해야 한다.
GRADING
총 40점에 해당하는 여러 테스트에서 N은 60을 넘지 않는다.
August 8 – 15, Plovdiv, Bulgaria
Contest Day 2 - Mecho
English 1.1