OI题库

【问题描述】

       传送门是一个非常有趣的解谜游戏，你位于一个N行M列的迷宫中，这个迷宫有一个宝藏，你希望用尽可能少的移动得到宝藏。

       你可以移动到相邻的四个格子中的空格，或者利用传送门来移动。具体来说，你有一把激光枪，它可以创造两种传送门，黄色传送门和蓝色传送门。每次你可以朝东南西北中的某个方向发射一个能量球，当它击中第一个障碍时会消失并在被击中处形成一个传送门（能量球击中宝藏会直接穿过去）。

       当且仅当创造了黄色传送门和蓝色传送门之后，你可以进入其中任意一个传送门然后从另一个传送门出来。

       考虑下面的迷宫（灰色格子表障碍，白色格子表空格，红点是你的位置）：

假设你向东发射蓝色传送门：

       然后向南发射黄色传送门：

       然后向南移动一步：

       现在是最有意思的部分，如果你再向南移动一步，那么你会穿过黄色传送门而到达蓝色传送门！

       当且仅当另一个同色传送门形成时，前一个传送门会消失，譬如你向西边发射一个蓝色传送门，旧的蓝色传送门便会消失：

       请注意，传送门是位于障碍的某一侧。如果一个障碍的西侧有一个传送门，那么你必须从西边进入这个传送门，否则你就是在撞墙……

       最后，两个传送门不允许叠在一起，否则它们都会因为能量冲突而消失。

       现在，给你迷宫的地图，你的初始位置，宝藏的位置，请你用尽可能少的移动得到宝藏。注意，发射传送门不计入移动。

【输入文件】

       第一行T表示数据组数，每组数据按如下格式：

       C_i,j用来描述每个格子：

1.  . 表示一个空格。

2.  # 表示一个障碍。

3.  O 表示你的初始位置。

4.  X 表示宝藏的位置。

保证每组数据中O和X(均为大写)出现且只出现一次。你可以认为迷宫之外的部分都是障碍并且可以用来创造传送门。

【输出文件】

       T行，每组数据一行。

对于每组数据，如果无法得到宝藏则输出：

否则按如下格式输出S表示最少的移动次数：

【输入样例】

3

4 7

.O..##.

.#.....

.#.####

.#...X.

4 5

O....

.....

.....

....X

1 3

O#X

【输出样例】

4

2

No

【样例解释】

   下面是第一个样例的一种最优方案：

1. 向东移动一步。

2. 向北发射蓝色传送门。

3. 向南发射黄色传送门。

4. 向北移动一步。（进入蓝色传送门并发生传送）

5. 向东发射蓝色传送门。（旧的蓝色传送门消失）

6. 向南移动一步。（进入黄色传送门并发生传送）

7. 向西移动一步。（得到宝藏）

【数据规模】

       两个测试点

编号	分值	时限	描述
1	40	10s	T<=200   N,M<=8
2	60	1s	T<=100   N,M<=50