Informatica Online Judge

  로봇미로 #2 [2353 / 0931]

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


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

[36th 양현민 (gs18075)]
Writer ID : [gs18075]

Background

로봇대회에서 지고만 준호는 알고보니 로봇이 1초만에 회전하고 움직이는게 불가능함을 깨달았다

회전하는데 p초 이동하는데 q초가 걸릴 때 도착하는데 걸리는 시간을 구하시오.

.....
#.#..
...#.
.#...
...#.

미로에서 .은 이동할 수 있는 칸을 나타내고, #은 이동할 수 없는 칸을 나타낸다.
이러한 미로가 주어졌을 때, (1,1)에서 출발하여 (N,M)의 위치로 이동할 때 걸리는 최소시간을 구하는 프로그램을 작성하시오.
한 칸에서 다른 칸으로 이동하거나 회전할 때 1초가 걸리며, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 9초가 지나야 (N,M)의 위치로 이동할 수 있다. 시작지점과 끝지점에서는 방향이 상관 없다.

만약 최소시간이 K초보다 오래걸린다면 -1을 출력한다.

Input

첫째 줄에 정수 N,M,K,p,q(2≤N,M≤10000, 1≤K≤3000,1≤p≤10,1≤q≤10)이 주어진다.
다음 N개의 줄에는 M개의 정수로 미로가 주어진다.

Output

첫째 줄에 걸리는 최소 시간을 출력한다. 도착이 불가능 한 경우 -1을 출력한다.

IO Example

입력
6 11 90 2 3
..#.#.....#
#.#..###...
#.#.....#..
#.##.#..#.#
...#...#...
.#...#.....

출력
67

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