P13471 [GCJ 2008 #3] Portal

Portal$^{\text{TM}}$ 是由 Valve Software 开发并发行的一款第一人称解谜/平台游戏。游戏的核心思想是在墙上创建两个传送门，然后通过一个传送门跳进去，从另一个传送门出来。本题与此类似，但不要求你玩过 Portal。 在本题中，你处于一个 $R$ 行 $C$ 列的网格中。此外，网格的某处有一块美味的蛋糕。你非常饿，希望用尽量少的步数到达蛋糕。你可以向北、南、东或西移动到一个空单元格。此外，你还可以在墙上创建传送门。 为了帮助你到达蛋糕，你有一把传送门枪，可以发射两种传送门：黄色传送门和蓝色传送门。通过向北、南、东或西方向射击传送门枪，可以发射能量球，在遇到的第一个墙上创建一个传送门。注意，在本题中，射击传送门枪不计为一次移动。如果你向蛋糕射击，能量球会直接穿过蛋糕。 在创建了一个黄色传送门和一个蓝色传送门后，你可以通过黄色传送门到达蓝色传送门，反之亦然。利用这些传送门，你也许能更快地到达蛋糕！只有在你创建了一个黄色和一个蓝色传送门后，才能使用传送门。 请参考下图的网格：  灰色格子表示墙，白色格子表示空单元格，红色圆圈表示你的位置。 假设你向东射击蓝色传送门。传送门会出现在能量球遇到的第一个墙上，如下图所示：  现在假设你向南射击黄色传送门：  接下来你向南移动一步：  有趣的部分来了。如果你再向南移动一步，你会通过黄色传送门到达蓝色传送门：  任意时刻只能存在一个黄色传送门和一个蓝色传送门。例如，如果你尝试向西创建一个蓝色传送门，原来的蓝色传送门会消失：  只有当你再次发射同色传送门时，原有的传送门才会消失。 注意，传送门是创建在墙的一侧的。如果一堵墙的东侧有一个传送门，你必须从东侧进入墙才能通过传送门。否则你只是撞到了一堵墙，这是不可能的。 最后，你不能在同一位置放置两个传送门。如果你试图在已有传送门的一侧再次放置传送门，第二个传送门将无法形成。 给定迷宫、你的初始位置和蛋糕的位置，判断你是否能到达蛋糕，并输出最少需要多少步。注意，射击传送门枪不计为移动步数。

输入的第一行为测试用例数 $N$。接下来有 $N$ 组测试数据。 每组测试数据的第一行为两个整数 $R$ 和 $C$，用空格分隔。接下来有 $R$ 行，每行包含 $C$ 个字符，表示地图： - . 表示空单元格； - \# 表示墙； - o 表示你的起始位置； - x 表示蛋糕的位置。 每组数据中恰好有一个 o 和一个 x。 网格外的所有单元格都视为墙，你可以用它们来创建传送门。

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

**样例解释** 以下是第一组数据的移动顺序（注意，射击传送门枪不计为移动步数）： - 向东移动一步。 - 向北射击蓝色传送门。 - 向南射击黄色传送门。 - 向北移动一步，通过蓝色传送门。 - 向东射击蓝色传送门。 - 向南移动一步，通过黄色传送门。 - 向西移动一步。 - 吃掉你美味多汁的蛋糕。 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 翻译