Problem Statement |
| | NOTE: This problem statement contains images that may not display properly if viewed outside of the applet.
"Twisted Matrix" is a strange game in which you are given a binary matrix (containing only '1' or '0') and must perform a series of twist operations in order to reach a certain goal matrix. A twist operation involves taking any 2x2 block inside the matrix and then rotating the elements within the block 90 degrees clockwise or counterclockwise.
The following image shows two consecutive twist operations performed on a initial matrix.
Little Johnny has won the first prize in a world wide Twisted Matrix tournament. Unfortunately, his friends do not believe him. The situation is not helped by the fact that little Johnny has a very bad memory and cannot clearly remember the last move he made in order to reach the goal matrix in the finals. He only partially remembers the last two matrices in the game. You are given matrices A and B. Each matrix is given as String[], the j-th character of the i-th element of each String[] describes the cell at row i, column j of the matrix. Each cell contains '0' or '1' if little Johnny remembers the number in that cell or '?' otherwise. Matrix B was the last matrix in the game and A was the matrix preceeding it, which means that performing one twist operation on A must transform it into B. Return a String[] representing the complete contents of the matrix B. If there are many valid solutions then return the lexicographically first solution. If no solution is possible then return an empty String[]. |
| |
Definition |
| | | Class: | TwistedMatrix | | Method: | solve | | Parameters: | String[], String[] | | Returns: | String[] | | Method signature: | String[] solve(String[] A, String[] B) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | The lexicographically first of two matrices is the one with the lexicographically earlier row at the first row at which they differ. |
| - | The lexicographically first of two rows is the one with the smaller cell at the first column at which they differ. |
| |
Constraints |
| - | A and B will each contain N elements, where N is between 2 and 30, inclusive. |
| - | Each element of A and B will contain M characters, where M is between 2 and 30, inclusive. |
| - | Each character in each element of A and B will be '1', '0' or '?'. |
| |
Examples |
| 0) | |
| | {"1000",
"0000",
"0000",
"0000"} | {"0000",
"?000",
"0000",
"0000"} |
| Returns: {"0000", "1000", "0000", "0000" } | |
|
| 1) | |
| | | Returns: {"01", "11" } | | Another possibility is {"11","10"} but {"01","11"} comes earlier lexicographically. |
|
|
| 2) | |
| | {"000",
"0?0",
"000"} | {"111",
"1?1",
"111"} |
| Returns: { } | |
|
| 3) | |
| | {"?1111",
"11111",
"11011",
"10111"} | {"?1111",
"11111",
"1??11",
"1??11"} |
| Returns: {"01111", "11111", "10011", "11111" } | |
|
| 4) | |
| | {"00111",
"00111",
"11111",
"11111"} | {"??1??",
"??1??",
"?????",
"?????"} |
| Returns: {"00111", "00111", "11111", "11111" } | | In order to get the lexicographically earliest solution, you must rotate the 2x2 block containing only zeros. Note that this movement does not modify the matrix, but it is still valid. |
|
|