Description

天才游戏设计师 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$，则没有解。

Input Format

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

保证输入地图均为好地图（如题面描述）。

Output Format

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

若有多种方案，可输出任意一种。

3
6 13 15
#############
#S..#..##...#
###.##..#.#F#
#...##.##.###
#.#.........#
#############
5 8 3
########
#S.....#
####...#
#F.....#
########
4 10 11
##########
#S#...#.F#
#...#...##
##########

Case #1: POSSIBLE
#############
#S..#..##...#
###.##..#.#F#
#...##.##.#.#
#.#.........#
#############
Case #2: IMPOSSIBLE
Case #3: POSSIBLE
##########
#S#...#.F#
#...#...##
##########

Hint

样例解释

样例输出展示了一组可能的答案，其他答案也可能是正确的。

样例第 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 完成。