Description

Sokoban 是一款著名的日本益智游戏。Sokoban 在日语中意为“仓库管理员”。在这款游戏中，你的目标是将箱子推到仓库中指定的位置。推箱子时，箱子的前后方都必须是空的。这是因为你在推箱子时需要站在箱子的后面，并且每次只能推一个箱子。你不能把箱子推出棋盘，也不能在推箱子时站在棋盘外。

例如，在下图中：

箱子 1 可以向任意四个方向推动，因为它四周的格子都是空的。箱子 2 只能向东或向西推动；它不能向北或向南推动，因为其南侧的格子不是空的。箱子 3 不能向任何方向推动。箱子 4 只能向东或向西推动，因为其南侧有一堵墙。

Sokoban 已被证明是一个 P-Space 完全 问题，但我们这里讨论的是一个更简单的变体。在我们的 EZ-Sokoban 变体中，箱子内部装有强力磁铁，必须几乎始终保持相互连接。在“稳定”状态下，所有箱子都必须边与边相连。也就是说，从任意一个箱子出发，都可以通过依次经过与其相邻的箱子，到达任意其他箱子。如果你推动了一个箱子，导致箱子们不再连通，你就进入了“危险模式”。在危险模式下，下一步推动必须使得所有箱子重新连通。

例如，在下图中：

当前状态是稳定的，因为所有 4 个箱子都通过边相连。假设你决定将最北边的箱子向西推动：

现在处于危险模式，因为最北边的箱子与其他箱子不再连通。下一步推动必须让箱子们重新变为连通状态。例如，你可以将最北边的箱子向南推动：

这样箱子们又重新连接，回到了稳定状态。

一个 Sokoban 谜题由棋盘、箱子的初始布局以及目标布局（即希望箱子最终达到的位置）组成。给定一个 EZ-Sokoban 谜题，请你求出使箱子移动次数最少的解，或者判断该谜题无解。初始和目标布局都不会处于“危险模式”。

为了简化问题，假设你（仓库管理员）可以随时跳到棋盘上的任意空位。

Input Format

输入文件的第一行包含一个整数 $T$，表示测试用例的数量。

每个测试用例包含若干行。第一行为 $R$ 和 $C$，分别表示棋盘的行数和列数，用一个空格分隔。接下来 $R$ 行，每行包含 $C$ 个字符，描述棋盘：

• '.' 表示空格
• '#' 表示墙
• 'x' 表示目标点（箱子最终应在此处）
• 'o' 表示箱子
• 'w' 表示箱子和目标点重合

箱子的数量等于目标点的数量。

Output Format

对于每个测试用例，输出

Case #$X$: $K$

其中 $X$ 是测试用例编号（从 1 开始），$K$ 是解题所需的最少箱子移动次数。如果无解，则输出 $-1$。

4
5 4
....
#..#
#xx#
#oo#
#..#
7 7
.######
.x....#
.x....#
..#oo.#
..#...#
.######
.######
4 10
##########
#.x...o..#
#.x...o..#
##########
3 4
.#x.
.ow.
....

Case #1: 2
Case #2: 8
Case #3: 8
Case #4: 2

Hint

限制条件

• $1 \leqslant T \leqslant 50$
• $1 \leqslant R, C \leqslant 12$

小数据集（7 分）

• 时间限制：3 秒
• $1 \leqslant$ 箱子数量 $\leqslant 2$

大数据集（10 分）

• 时间限制：5 秒
• $1 \leqslant$ 箱子数量 $\leqslant 5$

翻译由 ChatGPT-4.1 完成。