TopCoder problem "MatrixGame" used in SRM 466 (Division II Level Three)

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 String[] containing N elements. The j-th character in the i-th element of this String[] 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 String[] 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 String[] matrix describing the grid that Alex initially has, return the lexicographically smallest String[] that he can produce.

Definition

Class:	MatrixGame
Method:	getMinimal
Parameters:	String[]
Returns:	String[]
Method signature:	String[] getMinimal(String[] matrix)
(be sure your method is public)

Notes

A String[] A is lexicographically smaller than a String[] 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

{"000",
 "000",
 "000"}

Returns: {"000", "000", "000" }

Any move has no effect.

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

{"111",
 "111",
 "111"}

Returns: {"111", "111", "111" }

{"01010",
 "10101",
 "01010",
 "10101"}

Returns: {"00011", "00011", "11100", "11100" }

{"11010100",
 "11110001",
 "00011101",
 "11111111",
 "01110100",
 "10000110",
 "00001001",
 "11010111"}

Returns: 
{"00000011",
"00001111",
"00110100",
"01011100",
"01111101",
"11001100",
"11011001",
"11111111" }

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14150&pm=10861

Writer:

Chmel_Tolstiy

Testers:

PabloGilberto , ivan_metelsky , zhuzeyuan

Problem categories:

Brute Force, Sorting, String Manipulation