Informatica Online Judge

  집탈출 [2098 / 0832]

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


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

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

Background

경곽이의 집은 H*W크기의 2차원 사각형으로 표현될 수 있다. 어느날 집에서 놀고있던 경곽이의 집에 프레디가 찾아왔다. 경곽이는 생존을 위해 집을 탈출해야 한다.

경곽이는 평소에 집을 꾸미기를 좋아해서 집에 벽이 많다. 또한 출입은 단 1대 있는 엘리베이터로만 가능하다.

경곽이의 집은 아래 조건을 따라 표현된다.
(이동 가능한 곳)경곽이가 이동할 수 있는 공간 : 0
(이동 불가능한 곳)벽 : 1
(출발점)경곽이가 놀고있던곳 : 2
(도착점)엘리베이터의 위치 : 3

경곽이는 놀라서 다리에 쥐가 난 상태다. 따라서 1번에 상하좌우로 2칸씩만 움직일 수 있다.(단 이동 방향에 벽이 있다면 벽 직전까지만 움직인다.)

경곽이의 집은 가장자리가 모두 벽으로 둘러쌓여 있음이 보장된다.

Input

첫 줄에는 H,W가 순서대로 들어온다.
(H,W <= 100)
다음 H줄에는 각각 경곽이의 집 상태를 나타내는 W개의 숫자가 입력된다.

Output

경곽이가 집을 탈출하기 위한 최소 시간을 출력하시오.
(단 경곽이는 2칸을 움직이는데 1초가 걸리며, 이동방향에 벽이 있어 1칸만 움직이는 경우도 1초가 소모된다.)
만약 탈출이 불가능한 경우 -1을 출력하시오.

IO Example

<입력 예1>
5 3
1 1 1
1 2 1
1 3 1
1 0 1
1 1 1

<출력 예 1>
-1

<해설 1>
경곽이는 (2,2)에서 출발한다.
1초가 지난 후 경곽이는 (2,2)->(2,4)로 움직이게 되며, 1초가 더 지난 후 경곽이는 다시 (2,4)->(2,2)로 이동한다. 이를 계속 반복해도 엘리베이터에는 도착할 수 없으므로 출력은 -1이 된다.

<입력 예 2>
5 5
1 1 1 1 1
1 2 1 0 1
1 0 3 1 1
1 1 1 0 1
1 1 1 1 1

<출력 예 2>
2

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