TheSquareDivOne

SRM 457 · 2009-11-12 · by vexorian

SRM 457 · 2009-11-12 · by vexorian · Graph Theory

Show categories

Class Name: TheSquareDivOne

Return Type: String[]

Method Name: solve

Arg Types: (vector<string>)

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.

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

{"...",
 "...",
 "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.

{
".....",
".....",
".CCCC",
".....",
"....."
}
Returns: {".....", "..C..", "..C..", "..C..", "..C.." }

{
".....",
".....",
"CCCC.",
".....",
"....."
}
Returns: {".....", "..C..", "..C..", "..C..", "..C.." }

{"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

{"C..",
 ".C.",
 "..C"}
Returns: {"C..", ".C.", "..C" }

No move is necessary.

144)

{"CCCCCCCCCCCCCCCCCC",
 ".CCCCCCCCCCCCCCCCC",
 "..CCCCCCCCCCCCCCCC",
 "...CCCCCCCCCCCCCCC",
 "....CCCCCCCCCCCCCC",
 ".....CCCCCCCCCCCCC",
 "......CCCCCCCCCCCC",
 ".......CCCCCCCCCCC",
 "........CCCCCCCCCC",
 ".........CCCCCCCCC",
 "..........CCCCCCCC",
 "...........CCCCCCC",
 "............CCCCCC",
 ".............CCCCC",
 "..............CCCC",
 "...............CCC",
 "................CC",
 ".................C"}
Returns: {"CCCCCCCCCCCCCCCCCC", "CCCCCCCCCCCCCCCCC.", "CCCCCCCCCCCCCCCC..", "CCCCCCCCCCCCCCC...", "CCCCCCCCCCCCCC....", "CCCCCCCCCCCCC.....", "CCCCCCCCCCCC......", "CCCCCCCCCCC.......", "CCCCCCCCCC........", "CCCCCCCCC.........", "CCCCCCCC..........", "CCCCCCC...........", "CCCCCC............", "CCCCC.............", "CCCC..............", "CCC...............", "CC................", "C................." }

crafted cases begin here

Submissions are judged against all 176 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class TheSquareDivOne with a public method vector<string> solve(vector<string> board) · 176 test cases · 2 s / 256 MB per case