P16855 [GKS 2021 #E] Palindromic Crossword

A crossword puzzle is a rectangular grid of black cells and letters A-Z like the one shown below. :::align{center}  ::: Words in the crossword are defined as maximal vertical or horizontal segments of characters. In the crossword below, `DO` and `ON` are examples of words. :::align{center}  ::: A palindromic crossword is one where every word is a palindrome. Let $R_{i,j}$ represent the character on the $i$-th row and $j$-th column, where $i$ and $j$ are $1$-indexed. The top left corner is $R_{1,1}$. In the example palindromic crossword below, the `B` in $R_{3,2}$ is part of both the horizontal word starting at $R_{3,1}$ and the vertical word ending at $R_{4,2}$, and both are palindromes. :::align{center}  ::: You have been gifted a palindromic crossword puzzle with $N$ rows and $M$ columns. You finished the crossword and throw away the clues, preparing to hang it on your wall. However, you accidentally erase some of the letters! You want to recover as much of the crossword as possible, but you do not have the clues anymore. Using only the knowledge that the crossword is palindromic, restore the maximum possible number of missing characters in the given crossword. Missing letters are represented as empty white cells in the below diagram. The crossword on the left is the crossword you are given and the crossword on the right is the result after you recover as many letters as possible. The remaining cells cannot be filled because we do not have sufficient information to recover them. :::align{center}  :::

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. The first line of each test case contains two integers, $N$ and $M$, representing the number of rows and columns in the crossword, respectively. The next $N$ lines represent the $N$ rows of the grid. The $i$-th row consists of $M$ characters representing $R_{i,1}$, $R_{i,2}$, ..., $R_{i,M}$. Each character is one of the following: - A capital letter of the alphabet ($A$-$Z$) - A period (`.`) for a missing letter (empty white cell in the example crossword) - A hash (`#`) for black cell

For each test case, output one line containing Case #$x$: $y$ where $x$ is the test case number (starting from $1$) and $y$ is the number of empty white cells that were filled. Then, output $N$ more lines representing the final grid, with the missing characters (`.`) replaced by capital letters ($A$-$Z$) where possible.

In Sample Case #$2$, we are able to fill in $8$ of the blanks. We can fill in the missing letters as follows: - row $1$, column $4$: We know this is `A` from character at row $1$, column $1$. - row $2$, column $4$ = `A` from row $1$, column $4$. - row $2$, column $6$ = `A` from row $2$, column $4$. - row $3$, column $6$ = `A` from row $2$, column $6$. - row $3$, column $2$ = `B` from row $3$, column $1$. - row $4$, column $2$ = `B` from row $3$, column $2$. - row $4$, column $3$ = `B` from row $4$, column $2$. - row $4$, column $4$ = `A` from row $4$, column $1$. ### Limits $1 \le T \le 100$. There exists at least one way to fill in the given input grid such that it is a palindromic crossword. All characters in the grid are in the set $\{\texttt{A-Z}, \#, .\}$. **Test Set 1** $1 \le N, M \le 50$. **Test Set 2** For at most $10$ cases: $1 \le N, M \le 1000$. For the remaining cases: $1 \le N, M \le 50$.