타임 트라이얼

컴퓨터 게임을 극도로 짧은 시간 안에 끝내는 것을 좋아하는 사람이 있다. Terry A. Smith도 그중 하나이며, 특히 롤플레잉 게임을 선호한다.

그는 지금 롤플레잉 게임의 주요 이벤트 중 하나를 더 짧게 공략할 방법을 찾고 있다. 이 이벤트에서는 바위 세 개와 표시된 칸 세 개가 있는 격자 지도 위에서 일종의 퍼즐이 주어진다. 게임의 주인공을 적절히 조작해 모든 바위를 표시된 칸 위에 놓는 것이 목표다.

그림 1: 지도 예시

주인공은 벽이나 바위에 가로막히지 않는 한 동서남북으로 인접한 네 칸으로 이동할 수 있다. 벽이 있는 칸에는 절대 들어갈 수 없다. 반면 바위가 있는 칸으로 이동할 때는 이동 방향으로 바위를 민다. 다만 바위 너머 칸이 벽이나 다른 바위면 바위를 밀 수 없고, 이때 이동은 가로막힌다. 또한 한 번에 바위 하나만 움직일 수 있다. 바위가 표시된 칸을 지나가는 것은 허용된다.

Terry는 바위를 움직이는 최적의 방법을 찾아 그대로 이벤트를 플레이하면 플레이 시간을 줄일 수 있다고 생각한다. 그러나 이 퍼즐의 해를 손으로 찾는 것은 그에게 너무 어렵다. 그래서 그는 입력으로 주어지는 지도마다 최소 걸음 수를 구하는 프로그램을 작성해 달라고 요청했다. 여기서 한 칸에서 인접한 칸으로의 이동 한 번이 한 걸음으로 센다.

입력은 데이터셋의 나열이다. 각 데이터셋은 다음 형식을 따른다.

W H
Row1
...
RowH

W와 H는 지도의 너비와 높이다 (4 ≤ W, H ≤ 16). Rowi는 지도의 i번째 행이며 W개의 문자로 이루어진다. 각 문자는 칸 하나를 나타내며 다음 중 하나다: ‘#’ (벽), ‘.’ (바닥), ‘*’ (바위), ‘_’ (표시된 칸), ‘@’ (주인공). 각 지도에는 바위가 정확히 세 개, 표시된 칸이 세 개, 주인공이 한 명 있다. 가장 바깥쪽 칸은 항상 벽이다. 벽이 아닌 칸의 수는 50을 넘지 않는다고 가정할 수 있다. 또한 모든 지도에 해가 적어도 하나 존재함이 보장된다.

입력은 0 두 개로 이루어진 줄로 끝난다. 이 줄은 어떤 데이터셋의 일부도 아니며 처리해서는 안 된다.

각 데이터셋마다 최소 걸음 수를 한 줄에 출력한다.