문제1237-- 2보 전진을 위한 1보 후퇴

1237: 2보 전진을 위한 1보 후퇴

시간제한 : 1.000 sec  메모리제한 : 128 MB

문제 설명

한국기술교육대학교에 오랜만에 놀러온 상엽이는 실수로 1공학관 앞에 있는 NxN 미로에 빠지고 말았습니다. 

그런데 기이하게도! 상엽이는 2보 전진을 하고 꼭 1보 후퇴하는 이상한 습관을 가지고 있었습니다.

따라서 상엽이는 반드시 2보 전진 후에는 1회 뒤로 가만 합니다.

위와 같은 상황에서 상엽이가 도착지까지 가장 빨리 가려면 얼마나 걸어야 하는지 이에 대해 출력해주세요. 

※ 시작 지점은 (1,1) 종료 지점은 (N,N)로 고정 됩니다.
※ 탈출 할 수 없는 경우 -1 을 출력합니다.

입력 설명

첫줄에 미로의 크기가 (N<=50)으로 주어집니다.

N줄 동안 N개의 숫자가 주어집니다.

0은 벽 1은 길입니다

출력 설명

도착지 까지 가장 빨리 도착하는 걸음의 수를 출력합니다.

입력 예시 Copy

3
1 1 0
0 1 0
0 1 1

출력 예시 Copy

8

도움

입력 1의 경우 

(1,1) -> ( 2,1) -> (2,2) -> (2,1) -> (2,2) -> (2,3) ->(2,2) ->(2,3) ->(3,3) 

로 총 8번의 걸음으로 도달 할 수 있습니다.

출처/분류