This challenge was inspired by the game Flood.
Challenge
Given a grid of colors, determine the optimal list of moves to take to convert the whole grid to the same color.
First of all, let us say that a pixel is in the "top left chunk" if and only if it is either the top left pixel or it shares an edge with a pixel of the same color in the top left chunk. Then, a move is defined as changing the color of all pixels in the top left chunk to a specific color.
If you change the color of the top left chunk to match the color of one of the pixels adjacent to the top left chunk, then that pixel joins the top left chunk.
The input will be given as a matrix of positive integers with each integer representing a distinct color. A move is defined by the color to which you change the top left chunk; thus, a move is represented as an integer,
The output should be a list of integers representing which moves to take to convert the entire grid to one color in as few moves as possible. If multiple methods are possible, outputting all of them or any one of them is allowed.
Example
Let's take this as an example:
123
132
223
In this case, both [2, 3, 2] and [3, 2, 3] work. We observe the following for [2, 3, 2]:
123 223 333 222
132 -> 232 -> 332 -> 222
223 223 333 222
and the following for [3, 2, 3]:
123 323 223 333
132 -> 332 -> 222 -> 333
223 223 223 333
Test Cases
123
132 -> 2 3 2 OR 3 2 3
223
111
111 -> []
111
123
231 -> 2 3 1 2
312
123
312 -> 2 1 3 1 2 OR 2 1 3 2 1 OR 2 3 2 1 3 OR 2 3 2 3 1 OR 3 1 2 1 3 OR 3 1 2 3 1 OR 3 2 3 1 2 OR 3 2 3 2 1 (Thanks @JonathanAllan)
231
Rules
- This is code-golf so the shortest valid submission is determined as the winner, tiebreak by earlier submission winning
- The input and output can be in any reasonable format for matrices and lists
- The input is not necessarily square but is necessarily rectangular
- Your program must be able to handle at least 128 x 128
- Your program must be able to handle at least 16384 colors
- You may also take the number of distinct colors as an input
Please correct my test cases if they are wrong. Thanks!
Note:
I believe that this is different enough from Create A Flood AI to warrant its own post because the winning criteria are very different; that one mainly asks to find a small number of steps to solve all of the test cases; this one requires one of the shortest solutions and is a code-golf. However, if you disagree, please close-vote as duplicate and then the community can decide.
