#4682. Sliding Block Puzzle

内存限制:256 MiB 时间限制:30 Sec

题目描述

在滑块拼图中,我们通过反复滑动滑块到空格位置来完成一个目标局面。一位拼图设计者结合滑块拼图和迷宫的思
想设计了一种新的拼图。拼图被表示成一个矩形区域,区域被划分成一些 1×1 的小格。其中一些小格被提前放置
了障碍,无法被滑动。剩下的位置里有两个小格是空的,以及一个 2×2 的王滑块与许多 1×1 的卒滑块。如果一
个卒滑块与一个空格相邻,则卒滑块可以移动到空格中。如果一个王滑块的一边两个小格都是空格,则王滑块可以
向这条边的方向移动。但是注意我们无法移动障碍。对于给定的初始拼图,拼图游戏的任务是将王滑块移动到整个
区域的左上角。
例如下图给出了第四组样例的初始局面。
 
你的任务是计算从给定局面到完成任务所需的最少移动次数。一次移动是指某种滑块移动到相邻的位置上。

输入格式

输入包含多组测试数据。每组数据的第一行包含两个正整数 H 和 W ,表示拼图的矩形区域包含 H×W 个小格。接
下来 H 行,每行 W 个字符,表示拼图,其中‘X’, ‘o’, ‘*’ 和 ‘.’ 分别表示王滑块、卒滑块、障碍和
空格。保证 3≤H,W≤50 。输入以两个零作为结束。

输出格式

对于每组数据,输出一行一个整数,如果给定局面能完成任务,则输出最小步数,否则输出-1。

样例

样例输入


			
3 3
oo.
oXX
.XX
3 3
XXo
XX.
o.o
3 5
.o*XX
oooXX
oooo.
7 12
oooooooooooo
ooooo*****oo
oooooo****oo
o**ooo***ooo
o***ooooo..o
o**ooooooXXo
ooooo****XXo
5 30
oooooooooooooooooooooooooooooo
oooooooooooooooooooooooooooooo
o***************************oo
XX.ooooooooooooooooooooooooooo
XX.ooooooooooooooooooooooooooo
0 0

样例输出


			
11
0
-1
382
6807

数据范围与提示