P13209 [GCJ 2016 Finals] Map Reduce

天才游戏设计师 Ben 正在为他即将发布的增强现实手游设计地图。最近，他制作了一张地图，用一个 $\mathbf{R}$ 行 $\mathbf{C}$ 列的矩阵表示。地图由若干 `.` 字符（表示空地）、若干 `#` 字符（表示不可通过的墙）、一个起点 `S` 和一个终点 `F` 组成。例如，地图可能如下所示： ``` ############# #S..#..##...# ###.##..#.#F# #...##.##.### #.#.........# ############# ``` 在 Ben 的游戏中，一条路径是一系列上下左右的步伐，从一个格子走到另一个格子，且不能经过任何不可通过的墙。 Ben 认为一张好地图需要满足以下条件： - 任意两个空地（包括起点和终点）之间都存在一条路径。 - 为了保证结构完整性，不可通过的墙必须在边上相连，而不能只是通过角相连。对于地图中的任意 $2 \times 2$ 区域，如果该区域恰好有两堵墙，这两堵墙必须在同一行或同一列。换句话说，不能存在如下两种 $2 \times 2$ 区域的墙分布： ``` #. .# .# #. ``` - 地图的边界只能由不可通过的墙组成。一个格子被认为是边界，如果它在最上/最下行，或最左/最右列。 最短路径长度指的是从起点到终点所需的最少步数。例如，上述例子的最短路径长度为 $17$ 步。 作为如此聪明的制图者，Ben 发现他设计的这张地图对朋友们来说太难了。他希望通过移除一些不可通过的墙来降低难度。具体来说，他想知道是否可以移除零个或若干墙，使得从起点到终点的最短路径恰好为 $\mathbf{D}$ 步，并且修改后的地图依然是好地图。注意，仅仅找到一条长度为 $\mathbf{D}$ 的路径是不够的，$\mathbf{D}$ 必须是最短路径长度。 例如，如果 $\mathbf{D}=15$，我们可以移除终点正下方的一堵墙，得到一个合法解： ``` ############# #S..#..##...# ###.##..#.#F# #...##.##.#.# #.#.........# ############# ``` 如果 $\mathbf{D}=5$，则没有解。

输入的第一行包含一个整数 $\mathbf{T}$，表示测试用例组数。接下来有 $\mathbf{T}$ 组测试用例。每组数据第一行为三个空格分隔的整数 $\mathbf{R}$、$\mathbf{C}$ 和 $\mathbf{D}$，分别表示地图的行数、列数，以及期望的最短路径长度。接下来 $\mathbf{R}$ 行，每行包含 $\mathbf{C}$ 个字符（为 `.`、`#`、`S` 或 `F`），表示 Ben 的地图。 保证输入地图均为好地图（如题面描述）。

对于每组测试用例，输出一行 `Case #x: y`，其中 $x$ 为测试用例编号（从 1 开始），$y$ 为 POSSIBLE 或 IMPOSSIBLE，分别表示能否通过移除若干堵墙（可为零）使得最短路径长度恰好为 $\mathbf{D}$，且修改后的地图依然是好地图。如果可行，继续输出 $\mathbf{R}$ 行，每行 $\mathbf{C}$ 个字符，表示新的地图。输出时，移除的墙用 `.` 替换原有的 `#`。 若有多种方案，可输出任意一种。

**样例解释** 样例输出展示了一组可能的答案，其他答案也可能是正确的。 样例第 1 组即为题面中的例子。 样例第 2 组中，可以移除一些墙使最短路径长度变为 2 或 4，但无法使其恰好为 3。 样例第 3 组中，最短路径本身就是 11 步，因此无需移除墙。 **限制条件** - $1 \leq \mathbf{T} \leq 100$。 - 每组数据恰好有一个 $\mathbf{S}$ 和一个 $\mathbf{F}$。 - 输入文件大小不超过 3MB。 **小数据集（测试集 1 - 可见）** - 时间限制：~~60~~ 15 秒。 - $3 \leq \mathbf{R} \leq 40$。 - $3 \leq \mathbf{C} \leq 40$。 - $1 \leq \mathbf{D} \leq 1600$。 **大数据集（测试集 2 - 隐藏）** - 时间限制：~~300~~ 75 秒。 - $3 \leq \mathbf{R} \leq 1000$。 - $3 \leq \mathbf{C} \leq 1000$。 - $1 \leq \mathbf{D} \leq 10^6$。 - 注意：大数据集的输出突破了 Code Jam 通常的输出大小限制，但你可以正常上传。 翻译由 GPT4.1 完成。