TopCoder problem "TheSquareDivOne" used in SRM 457 (Division I Level Three)



Problem Statement

    John and Brus like puzzles. They have been playing a new game which involves placing checkers on a square board. The board is a grid containing the same number of columns and rows.



The game begins with John placing checkers on specific cells of the board. Then, R[i] is calculated for each row i, where R[i] is the number of checkers in the i-th row. Brus must then move the checkers in such a way that for each column i in the final board, the number of checkers in that column is equal to R[i]. Note that R[i] is calculated for the initial placement of checkers and is not modified afterwards. In a single turn, Brus can move a checker up, down, left or right into an adjacent empty cell. He must use as few turns as possible to reach the goal.



You are give a String[] board, where the j-th character of the i-th element is uppercase 'C' if the cell at row i, column j contains a checker and '.' otherwise. Return the final placement of checkers using the same format as the input. Since there may be many possible final placements, return the one that comes first lexicographically.
 

Definition

    
Class:TheSquareDivOne
Method:solve
Parameters:String[]
Returns:String[]
Method signature:String[] solve(String[] board)
(be sure your method is public)
    
 

Notes

-The lexicographically earlier of two String[]s is the one that has the lexicographically earlier String in the first position at which they differ.
-The lexicographically earlier of two Strings is the one that has the earlier character (using ASCII ordering) at the first position at which they differ.
-In ASCII ordering, a dot character '.' comes before 'C'.
 

Constraints

-board will contain exactly n elements, where n is between 1 and 18, inclusive.
-Each element of board will contain exactly n characters.
-Each element of board will contain only uppercase 'C' or '.'.
 

Examples

0)
    
{"...",
 "...",
 "C.."}
Returns: {"...", "...", "..C" }
Initially, R[0] = 0, R[1] = 0, R[2] = 1.

There is currently a checker in column 0 which must be moved to column 2. It can be done in two turns.
1)
    
{"CCC",
 ".C.",
 "CCC"}
Returns: {"C.C", "C.C", "CCC" }
CCC    CCC    C.C    C.C
.C. -> ..C -> .CC -> C.C
CCC    CCC    CCC    CCC


The following sequence also takes three turns, but its final placement does not come earlier lexicographically:



CCC    CCC    CCC    CCC
.C. -> C.. -> CC. -> C.C
CCC    CCC    C.C    C.C


2)
    
{"C..",
 ".C.",
 "..C"}
Returns: {"C..", ".C.", "..C" }
No move is necessary.
3)
    
{"C....","CCCCC","...CC",".CC..",".C.C."}
Returns: {".C...", "CCCCC", ".C..C", ".CC..", ".C.C." }

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10298

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14144&pm=10298

Writer:

vexorian

Testers:

PabloGilberto , ivan_metelsky , Chmel_Tolstiy

Problem categories:

Graph Theory