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

样例输出

#4682. Sliding Block Puzzle

题目描述

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示