EZ-Sokoban

Sokoban은 유명한 일본 퍼즐 게임이다. Sokoban은 일본어로 "창고지기"라는 뜻이다. 이 게임의 목표는 상자를 창고 안의 지정된 위치로 미는 것이다. 상자를 밀려면 상자의 뒤쪽과 앞쪽 공간이 비어 있어야 한다. 상자를 밀 때 그 뒤에 서 있어야 하며 한 번에 상자 하나만 밀 수 있기 때문이다. 상자를 보드 밖으로 밀 수 없으며, 상자를 밀 때 보드 밖에 서 있을 수도 없다.

예를 들어 다음 그림에서:

상자 1에 인접한 네 공간이 비어 있으므로 이 상자를 네 방향 중 어느 방향으로든 밀 수 있다. 상자 2는 동쪽이나 서쪽으로만 밀 수 있다. 남쪽 공간이 비어 있지 않으므로 북쪽이나 남쪽으로는 밀 수 없다. 상자 3은 어느 방향으로도 밀 수 없다. 상자 4의 남쪽에 벽이 있으므로 이 상자는 동쪽이나 서쪽으로만 밀 수 있다.

Sokoban은 P-Space 완전 문제임이 증명되었지만, 여기서는 더 쉬운 변형을 다룬다. 이 Sokoban 변형에서 상자 내부에는 강력한 자석이 있으며, 거의 항상 서로 붙어 있어야 한다. "stable" 조건에서는 모든 상자가 간선을 맞대어 연결되어 있어야 한다. 이는 어떤 상자에서든 간선을 공유하는 상자들을 거쳐 다른 어떤 상자로도 갈 수 있다는 뜻이다. 상자를 밀어 상자들이 더 이상 연결되어 있지 않게 되면 "위험 모드"가 된다. 위험 모드에서는 다음 밀기로 상자들이 다시 연결되게 해야 한다.

예를 들어 다음 그림에서:

4개의 모든 상자가 간선을 맞대어 연결되어 있으므로 상황은 안정적이다. 가장 북쪽에 있는 상자를 서쪽으로 밀기로 했다고 가정하자.

이제 가장 북쪽에 있는 상자가 다른 어떤 상자와도 연결되어 있지 않으므로 위험 모드이다. 다음 밀기로 안정된 위치로 되돌아가야 한다. 예를 들어 가장 북쪽에 있는 그 상자를 남쪽으로 밀 수 있다.

이렇게 하면 상자들이 다시 안정된 상태가 된다.

Sokoban 퍼즐은 보드, 상자들의 초기 배치, 그리고 최종 배치(마지막에 상자들이 놓이기를 원하는 위치)로 구성된다. EZ-Sokoban 퍼즐이 주어질 때, 상자 이동 횟수를 최소화하는 해를 찾거나 풀 수 없다고 판정하라. 최종 배치와 초기 배치는 "dangerous" 모드가 아니다.

문제를 단순화하기 위해 창고지기는 언제든 보드의 비어 있는 어느 위치로든 점프할 수 있다고 가정한다.

제한

메모리 제한: 1 GB.

1 ≤ T ≤ 50 1 ≤ R,C ≤ 12

작은 데이터 세트

시간 제한: 30초. 1 ≤ 상자의 수 ≤ 2

큰 데이터 세트

시간 제한: 45초. 1 ≤ 상자의 수 ≤ 5

입력 파일의 첫 번째 줄에는 케이스 수 T가 주어진다.

각 케이스는 여러 줄로 구성된다. 첫 번째 줄에는 보드의 행 수와 열 수인 R과 C가 하나의 공백으로 구분되어 주어진다. 이어서 R개의 줄이 주어진다. 각 줄에는 보드를 나타내는 C개의 문자가 주어진다.

• '.'은 빈 공간이다

• '#'은 벽이다

• 'x'는 목표 지점(마지막에 상자가 놓여야 하는 위치)이다

• 'o'는 상자이다

• 'w'는 상자이면서 목표 지점이다

상자의 수는 목표 지점의 수와 같다.

각 테스트 케이스마다 다음을 출력한다.

Case #X: K

여기서 X는 1부터 시작하는 테스트 케이스 번호이고, K는 퍼즐을 푸는 데 필요한 상자 이동 횟수의 최솟값이다. 퍼즐을 풀 수 없다면 -1이다.