P13173 [GCJ 2017 #2] Beaming With Joy

Joy 即将去度长假，因此她雇佣了技术人员为她安装一个基于红外激光束的安防系统。技术人员给了她一张图纸，将她的房子表示为一个 $R$ 行 $C$ 列的单元格网格。每个单元格包含以下之一： - `/`：一面双面镜，从单元格的左下角延伸到右上角。 - `\`：一面双面镜，从单元格的左上角延伸到右下角。 - `-`：一个水平激光发射器，会向该单元格左右相邻的单元格（如果有）发射水平激光束。 - `|`：一个垂直激光发射器，会向该单元格上下相邻的单元格（如果有）发射垂直激光束。 - `#`：一面墙。（注意，房子不一定被墙包围，这也是 Joy 需要安防系统的原因之一！） - `.`：空单元格，什么都没有。 激光束会沿直线传播，并穿过空单元格。当激光束遇到镜子时，会以 90 度角反射并继续传播。当向右传播的激光束遇到 `/` 镜子时，会反射并向上传播；而向上、向左或向下传播的激光束遇到 `/` 镜子时，会分别反射并向右、向下或向左传播。`\` 镜子的反射方式类似：当激光束向右、上、左或下传播时遇到它，会分别反射并向下、向左、向上或向右传播。当激光束遇到墙壁或超出网格边界时，会停止传播。激光束可以与其他激光束交叉，但如果激光束击中任何激光发射器（包括可能是发射该激光束的发射器本身），该激光发射器会被摧毁！ Joy 希望确保房子里的每个空单元格都至少有一束激光通过，并且没有任何激光发射器被摧毁，否则就浪费钱了！不幸的是，技术人员已经安装好了系统，所以 Joy 现在最多只能将一些现有的激光发射器旋转 90 度，也就是说，可以将任意数量（包括 0 个）的 `-` 改为 `|`，或将 `|` 改为 `-`。 你能帮 Joy 判断是否有办法达成她的目标，或者判断是否不可能实现吗？注意，不要求最小化旋转激光发射器的数量。

输入的第一行是测试用例数 $T$。接下来有 $T$ 组测试数据。每组数据的第一行为两个整数 $R$ 和 $C$，表示房子的网格有 $R$ 行 $C$ 列。接下来 $R$ 行，每行 $C$ 个字符，字符为 `/`、`\`、`-`、`|`、`#` 或 `.`，含义如题目描述所述。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 1 开始），$y$ 为 IMPOSSIBLE（如果 Joy 无法达成目标）或 POSSIBLE（如果可以达成目标）。如果可能，请在接下来的 $R$ 行输出修改后的网格（与输入格式相同），其中可以有若干 `-` 被替换为 `|` 或反之。 如果有多种可行解，输出任意一种即可。

**样例解释** 注意，最后两个样例不会出现在 Small 数据集中。 在样例 1 中，如果一个激光发射器被设置为发射激光覆盖空单元格，则必然会摧毁另一个激光发射器。因此该情况为 IMPOSSIBLE。 在样例 2 中，最左侧的激光发射器必须旋转以覆盖空单元格。最右侧的激光发射器也必须旋转，以避免摧毁最左侧的激光发射器。 在样例 3 中，现有的激光发射器已经覆盖了所有空单元格且不会互相摧毁，因此直接输出输入网格即可。当然，给出的输出也是正确的。 在样例 4 中，一种可行解是将三个激光发射器全部旋转。不过，以下解也是可行的： ``` .-. |// .-. #\/ ``` 因为镜子所在的单元格不需要有激光通过。（毕竟没人会偷巨大的斜面镜子，对吧？） 在样例 5 中，无论激光发射器如何旋转，都会自我摧毁，因此该情况为 IMPOSSIBLE。 **数据范围** - $1 \leq T \leq 100$。 - $1 \leq C \leq 50$。 - 网格中的每个字符为 `/`、`\`、`-`、`|`、`#` 或 `.`。 - 网格中 `-` 和 `|`（即激光发射器）的总数在 $1$ 到 $100$ 之间。 - 至少有 $1$ 个 `.`（即空单元格）。 **小数据集（测试集 1 - 可见）** - $1 \leq R \leq 5$。 - 网格中没有 `/` 或 `\`（即没有镜子）。 **大数据集（测试集 2 - 隐藏）** - $1 \leq R \leq 50$。 由 ChatGPT 4.1 翻译