Informatica Online Judge

  멀록 대행진의 마지막 장면에 [2214 / 08A6]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 1   Total Tried : 1


The Champion of this Problem (C++) : gs16042 - 0ms / 4072byte
My Best Submission (C++) : N/A

[35th 박준호]
Writer ID : [gs16042]

Background

시공의 폭풍 속에는 서로의 "핵"을 파괴하는 전쟁이 항상 일어난다. 어느 날, 우리의 꼬마 멀록 "머키" 또한 이 전쟁에 참가하게 되었다.

머키는 적의 핵을 파괴하기 위해 가장 빠른 시간 내에 핵에 도달하고자 한다. 그러나 "라그나로스"라는 불의 정령들은 머키를 방해하려고 하였다.

그들은 이동할 수는 없지만, 전장에 용암을 흘려 보내어 머키가 핵으로 갈 수 없게 하였다.

다행히 머키에게는 엄청난 힘이 있었다! 머키는 자기가 살아있을 때 자신이 서있는 곳에 알을 하나 깔 수 있는데, 자기가 죽게 되면 T초(0<=T<=10) 뒤에 다시 이 알에서 부활할 수 있다.

또한, 이 알은 용암의 영향을 받지 않아 부숴지거나 이동되지 않는다. 용암은 머키를 죽이게 되면 힘을 잃어 사라지게 되고, 다시 라그나로스들이 있는 곳에서 용암이 흐르기 시작한다.

머키가 활약하는 전장은 N*M의 직사각형이다(1<=N,M<=100). 각 격자는 이동할 수 있는 격자 O와 이동할 수 없는 격자 X로 표현되며, 머키의 위치 S와 라그나로스들의 위치 L이 주어진다(1<=L개수<=10).

머키는 매 초 상하좌우로 1칸 이동할 수 있으며, 매 초 용암은 인접한 이동 가능한 칸으로 확장한다. 위치에서 상하좌우로 빈 공간으로 1칸 흐른다(핵이 있는 위치와 머키가 있는 위치로도 흐른다).

용암은 머키가 죽을 경우 1초 뒤에 모두 사라지며, 라그나로스들의 위치에서 다시 흐르기 시작한다.

머키는 다른 격자로 이동하기 전에 알 하나를 자신의 위치에 깔 수 있다. 이 알은 부숴지거나 이동되지 않으며, 머키가 살아있는 동안 오직 하나만 깔 수 있다.

머키는 죽을 경우 정확히 T초 후에 알을 까고 나와 부활하게 되며, 알은 사라진다.

즉, 다시 새로운 위치에 알을 깔 수 있는 것이다. 머키는 가장 짧은 시간에 가장 적게 알을 깔아서 핵까지 도달하고자 한다.

머키의 위치는 S, 라그나로스의 위치는 L, 알의 위치는 G, 핵의 위치는 E이다.
5*5 맵에서 머키가 부활하는 시간이 1초로 주어지고, 맵이 다음과 같이 주어졌자고 해보자.

OOLOO
OOOOO
SOOOE
OOXOO
OOOOO

1초 후
OLLLO
OOLOO
OOOOE
SOXOO
OOOOO

2초 후
LLLLL
OLLLO
OOLOE
OOXOO
SOOOO

3초 후
LLLLL
LLLLL
OLLLE
OOXOO
OSOOO

4초 후
LLLLL
LLLLL
LLLLL
OLXLO
OOSOO

5초 후
LLLLL
LLLLL
LLLLL
LLXLL
OLGLO
머키는 용암에 죽게 되고, 1초 뒤 용암은 사라지고 머키가 부활하게 된다.

6초 후
OOLOO
OOOOO
OOOOE
OOXOO
OOSOO

7초 후
OLLLO
OOLOO
OOOOE
OOXOO
OOOSO

8초 후
LLLLL
OLLLO
OOLOE
OOXSO
OOOOO

9초 후
LLLLL
LLLLL
OLLLE
OOXGO
OOOOO
머키가 한번 더 죽고, 1초 뒤 용암이 사라지고 머키는 다시 알에서 부활하게 된다.

10초 후
OOLOO
OOOOO
OOOOE
OOXSO
OOOOO

11초 후
OLLLO
OOLOO
OOOSE
OOXOO
OOOOO

12초 후
LLLLL
OLLLO
OOLOS
OOXOO
OOOOO
12초만에 알 까기 2번으로 핵까지 도착하였다.

Input

첫 번째 줄에 전체 전장의 크기 N, M와 머키가 죽고 부활하기까지의 시간 T가 주어진다. 그 후 N줄에 걸쳐 전체 맵이 입력된다. O는 이동 가능한 격자, X는 이동 불가능한 격자이며, 머키의 위치는 S, 핵의 위치는 E, 라그나로스들의 위치는 L이다.

Output

머키가 핵에 도달한 최단 시간과, 이 때 머키가 알을 깐 최소 개수가 공백으로 출력된다.

IO Example

입력 예시)
5 5 1
OOLOO
OOOOO
SOOOE
OOXOO
OOOOO

출력 예시)
12 2



Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]