BAZE RUNNER
시간 제한1초메모리 제한256 MB
너비 4인 미로의 각 중간 행에는 통로가 하나씩 있고, 벽을 좌우로 한 칸 돌릴 수도 있을 때 왼쪽 위에서 오른쪽 아래까지 가는 최소 동작 수를 구한다.
문제
제2차 BAZE RUNNER(Bit MAZE RUNNER) 대회에 참가하게 된 세영이는 이번에야말로 우승하겠다고 다짐한다. BAZE RUNNER는 N×4 크기의 미로에서 진행하는 게임으로, 제일 왼쪽 위 칸에서 시작해 제일 오른쪽 아래 칸에 도착하면 승리한다. 미로의 제일 위 줄과 제일 아래 줄에는 벽이 없지만, 그 사이에 있는 모든 줄은 한 사람이 지나갈 만큼의 공간 하나를 제외하고 전부 벽으로 막혀 있다. 참가자는 단위 시간 동안 다음 두 가지 행동 중 하나를 할 수 있다.
- 벽이 아닌 인접한 칸으로 이동한다.
- 미로의 제일 왼쪽과 오른쪽 부분은 벽으로 막혀 있다.
- 자신의 아래 또는 위 줄의 벽들을 좌우로 한 칸씩 회전한다.
- 가장 왼쪽이나 오른쪽 칸의 벽이 밀려났다면 반대편 끝에서 나온다.
세영이가 우승하려면 도착까지 최소 몇 번의 행동을 해야 하는지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 미로의 크기 N(3 ≤ N ≤ 1000)이 주어진다.
다음 줄부터 N-2개의 줄에는 미로의 제일 위 줄과 제일 아래 줄을 제외한 각 줄의 정보가 주어진다.
줄은 0(길)과 1(벽)로 이루어진 4개의 비트로 구성되어 있으며, 각 줄에는 길이 정확히 하나만 존재한다.
출력
첫 번째 줄에 세영이가 우승하기 위한 행동의 최솟값을 출력한다.