BSSPC '21 S1 - Lakshy and Palindromic Rectangle
View as PDFIt is well known that while squares are bad, arithmetic is even worse for the mental health of highschool age children doing programming contests. For this reason, Lakshy's CCC (Competitive Computing Contest) mental health break entails the Palindromic Rectangle problem.
Given an
matrix of cells which either already contain a lowercase letter or are empty, determine values for each empty cell such that every row and column forms a palindrome.
Recall that a palindrome is a sequence of characters that reads the same backwards as forwards.
While Lakshy could totally do the problem himself, he is too busy struggling to read his poorly written IB HL chemistry notes. He leaves the task to you. Please write a program to help him solve the problem!
Constraints
Subtask 1 [10%]
Subtask 2 [90%]
No additional constraints.
Input Specification
The first line will contain two integers and
, the number of rows and columns of the grid, respectively.
The next lines will each contain
characters, representing the rows of the grid. Each character will either be a lowercase letter, or the symbol
., which indicates that the value is unspecified.
Output Specification
If no solution exists, output -1.
Otherwise, output lines consisting of
lowercase letters each, the correctly filled-in grid.
Any valid solution will be accepted.
Sample Input 1
3 3
iii
ooo
...Sample Output 1
iii
ooo
iiiExplanation for Sample 1
All of the rows (iii, ooo, iii) and all of the columns (ioi, ioi, ioi) form palindromes, so the solution is correct.
Sample Input 2
1 33
ccchasbecome........inrecentyearsSample Output 2
-1Explanation for Sample 2
It can be shown that there is no way to fill the empty grid cells such that the first row of the grid forms a palindrome, therefore a solution is impossible.
Comments
ccchasbecomeTERRIBLEinrecentyearsccchasbecome[REDACTED]inrecentyearsccchasbecomeunstableinrecentyears