창고지기라는 이름으로도 알려져 있는 소코반 게임은 유명한 고전 게임 중의 하나이다.

벽들로 막혀있는 지도상에서 사람을 움직여서 짐을 원하는 위치까지 밀어 운반하는 게임이다.

원래 게임에서는 여러 개의 짐을 여러 개의 목적지까지 하나씩 모두 옮기게 되어 있지만,

여기서는 간단하게 1개의 짐을 정해진 목적지까지 옮기는 것으로 하겠다.

지도는 위 그림처럼 격자로 되어있다. 검정색 상자를 x표시의 위치까지 옮기는 것이 게임의 목적이다.

이 때 빨간 선대로 상자가 움직이는 것이 최단 경로이다.

상자를 이렇게 움직이기 위해서 사람을 파란 선대로 이동시켜서 상자를 밀어야 한다.

물론 상자를 밀 때 앞쪽에 벽이 있으면 그 쪽으로 상자를 밀수가 없으며, 상자를 이동시킬 반대 방향의 칸에 사람이 위치에 있어야 한다.

게임 지도의 상황이 입력으로 주어질 때, 목적지까지 이동시키기 위해서 상자를 밀어야 하는 최소 횟수를 출력하는 프로그램을 작성하시오.

창고지기(socoban) timer 1s memory 64MB

창고지기(socoban) 1s 64MB