문제
고양이 톰과 생쥐 제리는 미로탈출 놀이를 하고 있다.
미로의 입구로 제리가 들어가는 것을 본 톰은 재빨리 제리를 추격하기 시작했다. 미로는 N * M 크기의 직사각형 모양으로 되어 있으며 N * M개의 정사각형 격자 모양으로 구성되어 있다. 각 격자에는 톰이나 제리가 통과할 수 있는 둥근 파이프가 놓여져 있는데 파이프가 입구와 출구가 서로 연결이 되어야 진입이 가능하다.
파이프의 모양은 일자 모양과 기역자 모양 두 가지가 있는데 방향에 따라 다음과 같이 번호를 부여하도록 하자.
미로의 입구는 왼쪽의 맨 위이며 출구는 오른쪽의 맨 아래쪽이다.
입구와 출구에는 언제든 들어가고 나올 수 있도록 파이프가 고정되어 있으나 나머지 위치에는 파이프가 무질서하게 놓여져 있다.
제리가 최대한 빠르게 출구로 빠져나갈 수 있도록 파이프를 정리해 주었을 때 제리가 통과해야 하는 격자의 수를 출력하는 프로그램을 작성하라.
각 파이프는 각각 90도씩 횟수 제한없이 회전이 가능하지만 한번 진입했던 격자에는 다시 들어갈 수 없다.
입력
입력의 첫 줄에는 행과 열의 크기 N과 M이 입력된다. (1 <= N, M <= 100)
둘 째 줄부터 N줄에 걸쳐 각 줄마다 M개의 정수가 입력되는데 각 위치에 놓인 파이프의 모양을나타낸다.
출력
각 위치의 파이프를 회전하여 입구부터 출구까지 이동이 가능하도록 할 때의 최소 이동거리(통과해야 하는 격자의 개수)를 출력한다.
통과할 수 있는 경로가 없다면 0을 출력한다.
예제
3 4
2 1 4 5
3 2 6 1
3 1 1 2
10
출처
jungol
로그인해야 코드를 작성할 수 있어요.