Algorithms: rearrange 2D matrix (via "flipping" element)
I'm wondering which algorithm solves the following (efficiently): a 2D matrix of numbers [1..9], which should be aligned horizontally from top (1) to bottom (9), but only through a click, either vertically or horizontally with a different number.
An example of an input matrix:
1 8 2 6 1 6
9 2 5 1 6 2
3 6 9 2 9 8
5 1 7 4 2 8
4 2 7 6 9 5
code>
Desired output matrix:
1 1 1 1 2 2
2 2 2 2 3 4
4 5 5 5 6 6
6 6 6 7 7 8
8 8 9 9 9 9
code>
Clarification in "Flipping": Take for example the input matrix. In the upper left corner is "1". That 1 can either flip horizontally with an 8 next to it (the first row becomes now 8 1 2 6 1 6
), or vertically and 9 is below (the first column becomes now 9 1 3 5 4
). He cannot flip diagonally 2.
Any solutions (any language is ok) to this problem?
source to share
The part about not being able to flip diagonally is the red herring. (Just flip the element next to it and then below it.) This way, any element can be exchanged with any other element in the matrix by repeated flips. Continue this line of reasoning and you will see that your desired end state is a matrix containing elements in ascending order, increasing from left to right and from top to bottom (as in the end state).
To get this end result quickly, simply change the original matrix from a 2D array to a flat list. Sort. Then go back to 2-dimensional array.
If you need to know the sequence of legal moves that can generate the final result (note that such a sequence is not unique!), The following simple algorithm will do it:
- Start by positioning the element that is in the upper left corner; this is the current position.
- Find the smallest element in the rest of the matrix.
- Drop this element until it reaches the column of the current position, then until it reaches the row of the current position.
- Mark the current position as correctly placed.
- Move to the next position by shifting the current position one index to the right, or to the beginning of the next line if an entire line was placed.
- Repeat until the entire matrix is installed.
Optimally efficient? Hardly. Simple and efficient? Quite right.
source to share
good puzzle! in any case, you can try modified versions of the sorting algorithms. I'm not very good at implementation, but I might try to give it to you later. Another way to solve this is through the A * algorithm. this is a pathfinding algorithm used in artificial intelligence, but I've seen it apply to a problem like this.
source to share