PROBLEM STATEMENT
Alex likes to play the following strange game. He starts with a rectangular NxM grid where each
cell contains a '0' (zero) or '1' (one). Rows of the grid are numbered 0 to N-1, inclusive, and
columns are numbered 0 to M-1, inclusive. On each move, he chooses two columns in the grid and
entirely swaps their content or he chooses two rows in the grid and entirely swaps their content.
He can perform an arbitrary large number of moves and there are no restrictions on the order in
which he performs moves.
Each NxM grid can be described as a vector containing N elements. The j-th character in
the i-th element of this vector is the same as the character in row i, column j of the
grid. Alex's goal is to achieve such a grid that the corresponding vector is
lexicographically minimal (see notes for exact definition). Since he is always unsure whether the
goal has been achieved, you are to write a program that checks it for him. Given a vector
matrix describing the grid that Alex initially has, return the lexicographically smallest vector
that he can produce.
DEFINITION
Class:MatrixGame
Method:getMinimal
Parameters:vector
Returns:vector
Method signature:vector getMinimal(vector matrix)
NOTES
-A vector A is lexicographically smaller than a vector B of the same length if
it contains a lexicographically smaller string at the first position where they differ.
-A string A is lexicographically smaller than a string B of the same length if it contains a
smaller character at the first position where they differ ('0' is smaller than '1').
CONSTRAINTS
-matrix will contain between 1 and 8 elements, inclusive.
-Each element of matrix will contain between 1 and 8 characters, inclusive.
-All elements of matrix will have the same length.
-Each character in matrix will be either '0' or '1'.
EXAMPLES
0)
{"000",
"000",
"000"}
Returns: {"000", "000", "000" }
Any move has no effect.
1)
{"010",
"000",
"110"}
Returns: {"000", "001", "011" }
The following sequence of moves can be used:
010 000 000 000
000 -> 010 -> 001 -> 001
110 110 101 011
2)
{"111",
"111",
"111"}
Returns: {"111", "111", "111" }
3)
{"01010",
"10101",
"01010",
"10101"}
Returns: {"00011", "00011", "11100", "11100" }
4)
{"11010100",
"11110001",
"00011101",
"11111111",
"01110100",
"10000110",
"00001001",
"11010111"}
Returns: {"00000011", "00001111", "00110100", "01011100", "01111101", "11001100", "11011001",
"11111111" }
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.