슬라이딩 블록 퍼즐

슬라이딩 블록 퍼즐에서는 틀 안의 조각(블록)을 빈 칸으로 반복해서 밀어 목표 배치를 만듭니다.

한 퍼즐 제작자가 슬라이딩 블록 퍼즐과 미로의 아이디어를 결합해 새로운 퍼즐을 만들었습니다. 퍼즐은 단위 정사각형으로 나뉜 직사각형 틀 안에서 진행됩니다. 일부 칸은 장애물이 미리 차지하고 있습니다. 틀 안에는 여러 조각이 있는데, 정확히 하나의 $2 \times 2$ 킹 조각과 여러 개의 $1 \times 1$ 폰 조각이 있습니다. 정확히 두 개의 $1 \times 1$ 칸이 빈 칸으로 남아 있습니다. 폰 조각이 빈 칸과 인접해 있으면 그 조각을 빈 칸으로 밀 수 있습니다. 킹 조각의 한 변 전체가 두 개의 빈 칸과 인접해 있으면 킹 조각을 그 방향으로 한 칸 밀 수 있습니다. 장애물은 움직일 수 없습니다. 주어진 초기 배치에서 시작하여, 목표는 킹 조각을 틀의 왼쪽 위 모서리로 옮기는 것입니다.

주어진 조각 배치에서 퍼즐을 푸는 데 필요한 최소 이동 횟수를 계산하는 프로그램을 작성하세요. 여기서 한 번의 이동이란 킹 조각 또는 폰 조각 하나를 인접한 위치로 미는 것을 뜻합니다.

입력은 여러 개의 데이터셋으로 이루어집니다. 각 데이터셋의 첫 줄에는 공백으로 구분된 두 정수 $H$와 $W$가 주어지며, $H$와 $W$는 각각 틀의 높이와 너비입니다. 이어지는 $H$개의 줄에는 각각 $W$개의 문자가 있어 조각의 초기 배치를 나타냅니다. 이 줄들에서 X, o, *, .는 각각 킹 조각의 일부, 폰 조각, 장애물, 빈 칸을 나타냅니다. 그 외의 문자는 나타나지 않습니다. $3 \le H \le 50$이고 $3 \le W \le 50$임을 가정해도 됩니다.

공백으로 구분된 두 개의 0이 있는 줄은 입력의 끝을 나타냅니다.

각 데이터셋에 대해, 킹 조각을 왼쪽 위 모서리로 옮기는 데 필요한 최소 이동 횟수를 한 줄에 출력하세요. 옮기는 것이 불가능하면 -1을 출력하세요.