SP7193 CURSE - The Pharaoh Curse

大多数参赛者都及时到达了 Benelux 算法编程竞赛现场，除了那些不走运选择了便宜导航系统的选手。由于几次错误的转弯，他们完全偏离路线，现在遍布世界各地。比如参赛者 J.-P. B.（他要求匿名）。长时间的驾驶后，他发现自己意外到了大西洋水下三英里。他一直盯着导航屏幕，直到感受到空气异常潮湿时才意识到情况不对。幸好，他座位下还有一艘备用潜艇，他顺利脱险。尽管这个故事看起来令人唏嘘，还有更糟的。另一位参赛者，我们称她为 S，决定坐火车出行。然而不幸的是，她还是听从了那个可恶的汽车导航的建议，结果误上了南行的火车。本应北行的她，被一系列错误指引带到了埃及法老 Sok-O-Ban 的金字塔迷宫中。经验丰富的冒险者都知道，这些古墓常常充满机关和陷阱。Sok-O-Ban 的墓穴也不例外。这位法老生前以喜好虐待著称，喜欢给陌生人设置不可能完成的挑战。因此，不难理解为什么 S 偶然被困在了一个四周全是坚硬岩石的封闭洞穴中。观察四周后，S 绘制了一张墓穴地图。幸运的是，她没有发现骷髅、木乃伊或致命陷阱。不过，她注意到地板上嵌入了一些按钮。只要她能同时按下所有按钮，隐藏的出口就会打开，一旦松开任何一个按钮，出口会再次关闭。除了按钮和一些积尘的地板外，还有两个装满石块的石棺。由于古埃及人身材矮小，石棺是边长为 1 米的立方体，与地面瓷砖大小一致。看起来石棺是解开谜题的关键：通过推动它们到按钮上，可以保持出口开启。问题在于，石棺太重无法手动搬动，也无法跨越。幸运的是，S 带了个便携式石棺运输装置。将这一系统安装在她的手臂上，就能轻松推动石棺直推进 1 米。这正好匹配她在地图上标记的 1 米网格。

输入的第一行是一个正整数，表示测试用例的数量。接下来每个测试用例包括： - 一行，包含两个正整数 $h, w \leq 50$，表示迷宫的高度和宽度。 - 接下来的 $h$ 行，每行有 $w$ 个字符，描述主角绘制的洞穴地图。地图符号说明： - `#` 表示墙壁或不可通行的区域。 - `.` 表示空地，最多有 100 个。 - `S` 表示主角的位置。 - `X` 表示一个沉重的石棺，图中最多有两个。 - `B` 表示一个按钮。 - `E` 表示出口。在地图边缘有且只有一个出口，且边缘只有墙和出口。

对于每个测试用例，输出一行，包含主角逃出迷宫所需的最小步数，如果无法逃脱则输出「impossible」。 **示例** ``` 输入： 3 7 8 ######## #..S...# #.####.# #.#.XB.# #.####.# #......E ######## 7 8 ######## #..S...# #.####.# #.#.BX.# #.####.# #......E ######## 4 8 ##E##### #...#### #SX.XBB# ######## 输出： impossible 10 19 ``` **本翻译由 AI 自动生成**