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

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

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

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

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

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

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

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

고돌이 고소미 timer 2초 memory 64MB

고돌이 고소미 2초 64MB