Informatica Online Judge

  로봇미로 #1 [2352 / 0930]

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


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

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

Background

준호는 자신이 만든 로봇으로 로봇미로를 탈출하는 대회에 출전하였다.
준호를 도와 로봇미로를 탈출하는데 걸리는 최소시간을 구하시오
N×M크기의 배열로 표현되는 로봇미로가 있다.

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

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

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

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

Input

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

Output

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

IO Example

입력
6 11 30
..#.#.....#
#.#..###...
#.#.....#..
#.##.#..#.#
...#...#...
.#...#.....

출력
25

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