# [Solution] Palindromic Crossword solution kickstart

## Palindromic Crossword solution kickstart

### Problem

crossword puzzle is a rectangular grid of black cells and letters A-Z like the one shown below.

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.

A palindromic crossword is one where every word is a palindrome. Let Ri,jRi,j represent the character on the ii-th row and jj-th column, where ii and jj are 11-indexed. The top left corner is R1,1R1,1. In the example palindromic crossword below, the B in R3,2R3,2 is part of both the horizontal word starting at R3,1R3,1 and the vertical word ending at R4,2R4,2, and both are palindromes. Palindromic Crossword solution kickstart

You have been gifted a palindromic crossword puzzle with NN rows and MM 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. Palindromic Crossword solution kickstart

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. Palindromic Crossword solution kickstart

### Input

The first line of the input gives the number of test cases, TTTT test cases follow. Palindromic Crossword solution kickstart
The first line of each test case contains two integers, NN and MM, representing the number of rows and columns in the crossword, respectively.
The next NN lines represent the NN rows of the grid. The ii-th row consists of MM characters representing Ri,1Ri,1Ri,2Ri,2Ri,MRi,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

### Output

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

### Limits

Time limit: 60 seconds.
Memory limit: 1 GB.
1T1001≤T≤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 {{A-Z#.}}

1N,M501≤N,M≤50.

#### Test Set 2

For at most 10 cases:
1N,M10001≤N,M≤1000.

For the remaining cases:
1N,M501≤N,M≤50.

### Sample

Sample Input
2
2 2
A.
.#
4 6
A...#.
B##...
B.###.
A...#.

Sample Output
Case #1: 2
AA
A#
Case #2: 8
A..A#.
B##A.A
BB###A
ABBA#.

In Sample Case #2, we are able to fill in 88 of the blanks. We can fill in the missing letters as follows:

• row 11, column 44: We know this is A from character at row 11, column 11.
• row 22, column 4=4= A from row 11, column 44.
• row 22, column 6=6= A from row 22, column 44.
• row 33, column 6=6= A from row 22, column 66.
• row 33, column 2=2= B from row 33, column 11.
• row 44, column 2=2= B from row 33, column 22.
• row 44, column 3=3= B from row 44, column 22.
• row 44, column 4=4= A from row 44, column 11.