고돌이 고소미

고돌이와 고소미는 고슴도치 마을에 사는 커플이다. 언제나처럼 둘은 만나면 ‘나 잡아봐라’ 게임을 하고 노는데 시간가는 줄 모른다. 아직 연애중인 둘은, 만나면 조금이라도 더 같이 있고 싶은데 저녁이 되면 집으로 돌아가야 하는 것이 아쉽다.

고슴도치 세계에도 통금은 있어 늦게 들어가면 부모님으로부터 꾸중과 제재를 받는다.

가능한 오래 놀다가 집에 가고 싶은 고슴도치 커플은 현재 위치에서 각자의 집으로 돌아가는 최단시간이 궁금하다.

고돌이와 고소미 커플을 위하여 이 시간을 구하는 프로그램을 작성해 보자.

편의상 고슴도치 마을은 모두 격자로 나뉘어져 있다고 가정한다. 또한 한 마리의 고슴도치는 1초에 최대 1칸까지 움직일 수 있는데 아래 그림과 같이 8곳 중에 한 곳으로 이동할 수 있다.

물론 마을의 경계를 벗어나거나 바닥이 깊게 파인 웅덩이들로는 이동할 수 없다. 그리고 이들이 고슴도치이기에 서로 너무 가까이 다가갈 수 없는 아픔이 있다고 한다.

각 고슴도치는 가시가 뻗은 영역이 아래 그림과 같이 주변 8곳이어서 다른 고슴도치가 이 영역으로 올 수 없다고 한다.

이것은 누구 하나가 집에 도착한 경우에도 적용된다.

입력

첫 행에 고슴도치 마을의 크기 N( 3 <= N <= 25)가 입력된다.

두 번째 행에 고돌이의 위치와 고돌이집의 위치가 공백으로 구분하여 입력된다.

세 번째 행에 고소미의 위치와 고소미집의 위치가 공백으로 구분하여 입력된다.

입력 순서는 행번호, 열번호 순서이며 행번호는 위에서부터 열번호는 왼쪽에서부터 매겨진다.

네 번째 행부터 N개의 행에 걸쳐 고슴도치 마을의 정보가 입력된다.

0이면 고돌이와 고소미가 이동할 수 있고 1이면 웅덩이로서 이동이 불가능한 곳이다.

고슴도치들이 집으로 돌아가지 못하는 경우는 주어지지 않는다.

출력

하나의 행에 고돌이와 고소미가 집으로 돌아가는 최단 시간을 출력한다.

예제1

예제2

출처

comkiwer

고돌이 고소미 2초 64MB