Informatica Online Judge

  무단외출 [2106 / 083A]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 9   Total Tried : 28


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

[koistudy.net (unkonwn)]
Writer ID : [gs16054]

Background

게임에 너무 중독된 나머지 저녁시간을 놓쳐버린 승한이는 너무 배가 고프기 때문에 무단외출을 해서 밥을 먹기로 결심했다.

하지만 저녁때는 선생님들이 항상 학교 주변을 지키기 때문에 위험하다. 시간이 얼마 남지 않았기 때문에 승한이는 최대한 빨리 들키지 않게 가야 한다.

n*m크기의 지도에서(0<=n,m<=100) 한 칸을 이동할 때마다 1의 시간이 들며 밥을 먹는데 t의 시간이 소모된다.

갔다 오는데 주어진 시간은 T이고 이를 넘으면 승한이는 자습시간에 늦게 된다.

상, 하, 좌, 우 4방향으로 이동 가능하며 정보 선생님들은 착하기 때문에 마주쳐도 1의 시간만 소모되지만 다른 선생님을 만나게 되면 꼼짝없이 잡히게 된다. 승한이가 늦지 않게 무사히 밥을 먹도록 도와주자. 단, 시작점과 끝점은 선생님이 안계신다.

Input

첫 줄에 승한이가 갈 수 있는 주변 범위의 세로 n, 가로 m이 주어진다.

두 번째 줄에는 총 주어진 시간 T와 밥먹는데 걸리는 시간 t가 주어진다.

다음 3번째 줄부터 n+3번째 줄까지 지도가 주어진다. 시작위치는 (1,1)이며 음식점은 (n,m)에 있다. 정보선생님은 1로, 다른 선생님은 2로, 이외에는 0으로 주어진다.

Output

승한이가 시간 내에 갈 수 있다면 걸리는 시간을 출력한다.

밥을 먹고 돌아올 수 있지만 늦게 된다면 “Too Late!”( “” 제외)를 출력한다.

선생님의 감시가 너무 심해서 걸리지 않고 음식점에 갈 수 없다면 “Oh No!”를 출력한다.

IO Example

입력1
5 5
30 7
0 0 0 2 0
0 1 0 1 0
0 1 0 2 0
0 1 1 2 0
0 0 1 1 0

출력1
25

입력2
5 5
20 7
0 0 0 2 0
0 1 0 1 0
0 1 0 2 0
0 1 1 2 0
0 0 1 1 0

출력2
Too Late!

입력3
5 5
20 7
0 0 2 0 0
0 0 2 0 2
0 1 2 1 1
0 0 0 2 0
0 0 0 2 0

출력3
Oh No!

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