Informatica Online Judge

  미로탈출 [2180 / 0884]

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


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[koistudy.net (33rd 최지원)]

Background

지원이는 $n*m$크기의 미로에 같히고 말았다.

현재 지원이의 위치는 ($1$, $1$)이며, 탈출하려면 ($n$, $m$)으로 가야한다.

지원이는 다음의 행동 중 하나를 할 수 있다.

1. 상하좌우로 1칸 이동한다. 시간이 1 걸리며 벽으로는 이동할 수 없다.
2. 어떤 위치에서나 부스터를 쓸 수 있는데, 벽을 1개 통과한 후 그 다음 벽 앞에서 멈춘다.(미로의 외부는 벽이 1칸 있다.) 시간은 1 걸리며 중간에 멈추지 못한다.

미로 밖에는 시공의 폭풍이 불고 있다.
따라서 지원이는 미로 밖으로 나가지 않고 가장 빨리 ($n$, $m$)으로 가는데 걸리는 시간을 구하려고 한다.

미로 밖은 1칸의 벽으로 둘러쌓여있으며 부스터로 벽을 뚫고 지나가도 지금 지원이의 위치를 제외하고 벽은 재생된다.

Input

미로의 크기인 $n$ $m$이 입력된다.
아래로 $n$줄에 걸쳐서 $m$개의 정수가 입력된다.

길은 0, 벽은 1로 표시된다.

[입력값의 정의역]

$1≤n,~m≤1000$

Output

출발지부터 도착지까지 걸리는 최소시간을 출력하라

IO Example

입력
3 2
0 0
0 0
0 0

출력
3

입력2
3 3
0 1 0
0 0 1
0 0 0

출력2
2

입력3
3 3
0 0 1
0 0 0
0 0 0

출력3
3

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