Informatica Online Judge

  대형선수학 레이스 [2265 / 08D9]

Time Limit(Test case) : 6000(ms)
Number of users who solved : 2   Total Tried : 2


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

[34th 김재홍]
Writer ID : [gs16017]

Background

경곽이는 기말고사를 위해 선형대수학을 공부하던 도중 지루했던 나머지 1장으로 돌아가 책을 처음부터 읽기 시작한다. 선형대수학 1장에는 벡터를 이용한 게임이 소개되어 있다. 규칙은 다음과 같다.
-------------
Ann과 Bert는 종이 위의 트랙에서 경주를 벌인다. 트랙이 충분히 넓다면 모양과 크기는 상관없다. 트랙에는 격자점이 표시되어 있고, 격자의 중심을 기준으로 이동하게 된다.
만일 누군가가 (a,b)만큼 움직이고 그 다음 (c,d)만큼 움직였다면, |a-c|<=1, |b-d|<=1이어야 한다.
이동할 때 현재 지점과 다음 지점을 잇는 선분 상의 모든 점이 트랙에 포함되지 않을 경우 이동은 유효하지 않다.
시작할 때에는 각자의 출발점에서 속도가 (0,0)인 채로 출발하며, 결승선을 먼저 통과하는 사람이 이긴다.
-------------
경곽이는 주어진 트랙에서 가장 빠르게 결승선에 도달할 때, 얼마의 시간이 걸리는지 궁금해졌다. 경곽이는 문제를 간단히 만들기 위해 승리 조건을 결승선을 통과하는 것 대신 결승점에 도착하는 것으로 바꾸고, 인원수를 1명으로 바꾸었다. 경곽이는 선형대수학을 이용해 이 문제를 풀어보려 했지만 매우 어려워 프로그래밍의 달인인 당신에게 부탁했다. 경곽이를 도와 문제를 해결해 보자.

Input

첫 줄에는 직사각형 영역의 높이 H와 너비 W가 주어진다. (1<=W,H<=200)
두 번째 줄 이후에는 직사각형의 각 격자점들이 공백을 사이에 두고 입력된다.
지나가지 못하는 지점일 경우 0, 출발점일 경우 2, 도착점일 경우 3, 그 외의 경우 1이 입력된다.

Output

결승점에 도달하는 최소 시간을 출력한다. 불가능하면 -1을 출력하라.

IO Example

입력
2 2
2 1
0 3

출력
1

해설
(0,0) -> (1,1)로 이동하면 된다.


입력
7 4
2 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
0 0 1 0
0 1 0 0
3 0 0 0

출력
6

해설
(0,0) -> (1,1) -> (2,2) -> (3,3) -> (3,3) -> (2,4) -> (0,6)으로 이동하면 된다.
두 번째 움직임에서 가속하면 세 번째 움직임에서 트랙 바깥으로 나가게 된다.


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

출력
10

해설
(8,10) -> (9,9) -> (10,7) -> (10,4) -> (9,2) -> (7,1) -> (4,1) -> (2,2) -> (1,4) -> (1,7) -> (2,10)

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