Map Reduce (Small)

Ben is a video game designer working on maps for his upcoming augmented-reality mobile game. He has just made a map that is a grid of $R$ rows and $C$ columns. Each cell is one of the following characters: . for an empty square, # for an impassable wall, S for the single start position, and F for the single finish position. For example, a map could look like this:

#############
#S..#..##...#
###.##..#.#F#
#...##.##.###
#.#.........#
#############

A path is a sequence of steps (up, down, left, or right) from one cell to another that never enters a wall.

Ben calls a map good if it has all of the following properties:

• There is a path between any two empty squares (the start and finish positions count as empty squares).
• Walls must meet at edges, not only at corners. For every $2 \times 2$ region of the map that contains exactly two walls, those two walls are in the same row or in the same column. In other words, no $2 \times 2$ region has its walls in either of these two configurations:

#.   .#
.#   #.

• Every boundary cell is a wall. A cell is on the boundary if it is in the top row, the bottom row, the leftmost column, or the rightmost column.

The length of the shortest path is the minimum number of steps needed to reach the finish position from the start position. In the example above, the shortest path takes 17 steps.

Ben thinks this map is too hard for his friends, so he wants to make it easier by removing some walls. He wants to know whether he can remove zero or more walls so that the resulting map is still good and the shortest path from start to finish takes exactly $D$ steps. It is not enough to find some path with $D$ steps: $D$ must be the length of the shortest path.

For example, if $D = 15$, removing the wall directly below the finish position gives a good map whose shortest path takes 15 steps:

#############
#S..#..##...#
###.##..#.#F#
#...##.##.#.#
#.#.........#
#############

If $D = 5$, there is no solution.

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case starts with a line containing three space-separated integers $R$, $C$, and $D$: the number of rows, the number of columns, and the desired length of the shortest path from start to finish after removing walls. $R$ lines follow, each with $C$ characters (., #, S, or F) that describe Ben's map.

The given map is guaranteed to be good.

Limits

• $1 \le T \le 100$
• Each test case contains exactly one S and exactly one F.
• The input file is at most 3 MB.
• $3 \le R \le 40$
• $3 \le C \le 40$
• $1 \le D \le 1600$

For each test case, output one line Case #x: y, where x is the test case number (starting from 1) and y is POSSIBLE or IMPOSSIBLE. The answer is POSSIBLE if some set of walls can be removed so that the map is still good and the shortest path takes exactly $D$ steps, and IMPOSSIBLE otherwise.

If the answer is POSSIBLE, output $R$ more lines of $C$ characters each: the map produced by the procedure below, with every removed wall written as ..

Let $L$ be the length of the shortest path in the current map. Cells are ordered row by row from the top, and from left to right within a row. A wall is a candidate if it is not on the boundary and the map is still good after removing only that wall. While $L \ne D$, repeat:

1. If some candidate wall's removal makes $L$ exactly 2 smaller, remove the first such wall in cell order.
2. Otherwise, remove the first candidate wall in cell order whose removal leaves $L$ unchanged.

If $L = D$ in the given map, no wall is removed. For every test case in this problem whose answer is POSSIBLE, this procedure always reaches $L = D$.

Sample case #1 is the example from the problem statement. Removing the wall directly below the finish position also gives 15 steps, but the wall directly to the left of the finish position comes earlier in cell order and its removal also makes the shortest path 2 steps shorter. The procedure therefore removes that wall.

In sample case #2, walls can be removed to make the shortest path take 2 or 4 steps, for example, but no way makes it take exactly 3 steps.

In sample case #3, the shortest path already takes 11 steps, so no wall needs to be removed.