Description

Portal$^{\text{TM}}$ 是由 Valve Software 开发并发行的一款第一人称解谜/平台游戏。游戏的核心思想是在墙上创建两个传送门，然后通过一个传送门跳进去，从另一个传送门出来。本题与此类似，但不要求你玩过 Portal。

在本题中，你处于一个 $R$ 行 $C$ 列的网格中。此外，网格的某处有一块美味的蛋糕。你非常饿，希望用尽量少的步数到达蛋糕。你可以向北、南、东或西移动到一个空单元格。此外，你还可以在墙上创建传送门。

为了帮助你到达蛋糕，你有一把传送门枪，可以发射两种传送门：黄色传送门和蓝色传送门。通过向北、南、东或西方向射击传送门枪，可以发射能量球，在遇到的第一个墙上创建一个传送门。注意，在本题中，射击传送门枪不计为一次移动。如果你向蛋糕射击，能量球会直接穿过蛋糕。

在创建了一个黄色传送门和一个蓝色传送门后，你可以通过黄色传送门到达蓝色传送门，反之亦然。利用这些传送门，你也许能更快地到达蛋糕！只有在你创建了一个黄色和一个蓝色传送门后，才能使用传送门。

请参考下图的网格：

灰色格子表示墙，白色格子表示空单元格，红色圆圈表示你的位置。

假设你向东射击蓝色传送门。传送门会出现在能量球遇到的第一个墙上，如下图所示：

现在假设你向南射击黄色传送门：

接下来你向南移动一步：

有趣的部分来了。如果你再向南移动一步，你会通过黄色传送门到达蓝色传送门：

任意时刻只能存在一个黄色传送门和一个蓝色传送门。例如，如果你尝试向西创建一个蓝色传送门，原来的蓝色传送门会消失：

只有当你再次发射同色传送门时，原有的传送门才会消失。

注意，传送门是创建在墙的一侧的。如果一堵墙的东侧有一个传送门，你必须从东侧进入墙才能通过传送门。否则你只是撞到了一堵墙，这是不可能的。

最后，你不能在同一位置放置两个传送门。如果你试图在已有传送门的一侧再次放置传送门，第二个传送门将无法形成。

给定迷宫、你的初始位置和蛋糕的位置，判断你是否能到达蛋糕，并输出最少需要多少步。注意，射击传送门枪不计为移动步数。

Input Format

输入的第一行为测试用例数 $N$。接下来有 $N$ 组测试数据。

每组测试数据的第一行为两个整数 $R$ 和 $C$，用空格分隔。接下来有 $R$ 行，每行包含 $C$ 个字符，表示地图：

• . 表示空单元格；
• # 表示墙；
• o 表示你的起始位置；
• x 表示蛋糕的位置。

每组数据中恰好有一个 o 和一个 x。

网格外的所有单元格都视为墙，你可以用它们来创建传送门。

Output Format

对于每组测试数据，输出一行，格式为 "Case #$X$: $Y$"，其中 $X$ 是测试用例编号，$Y$ 是到达蛋糕所需的最小步数。如果无法到达蛋糕，则输出 "THE CAKE IS A LIE"。

3
4 7
.O..##.
.#.....
.#.####
.#...X.
5 5
O....
.....
.....
.....
....X
1 3
O#X

Case #1: 4
Case #2: 2
Case #3: THE CAKE IS A LIE

Hint

样例解释

以下是第一组数据的移动顺序（注意，射击传送门枪不计为移动步数）：

• 向东移动一步。
• 向北射击蓝色传送门。
• 向南射击黄色传送门。
• 向北移动一步，通过蓝色传送门。
• 向东射击蓝色传送门。
• 向南移动一步，通过黄色传送门。
• 向西移动一步。
• 吃掉你美味多汁的蛋糕。

Portal$^{\text{TM}}$ 是 Valve Inc. 的商标。Valve Inc. 未参与本题的设计，也未对 Google Code Jam 进行任何背书。

小数据集（10 分，测试集 1 - 可见）

• $N=200$
• $1 \leqslant R, C \leqslant 8$

大数据集（15 分，测试集 2 - 隐藏）

• $N=50$
• $1 \leqslant R, C \leqslant 15$

由 ChatGPT 4.1 翻译