Help with DP algorithm

Fri, 21 Jan 2011 12:05:55 -0700

Hi all,

I am looking for some guidance on how to go about constructing (and coding) and algorithm that solves the following puzzle:

There are 6 colors, randomly ascribed to the cells of an NxM grid. The goal is, beginning with the color in the upper-left corner (let's call it 0,0), change the entire grid to one solid color in the smallest number of turns. Adjacent cells with the same color become a blob, such that all connected cells of the same color as 0,0 will change.

Thus, if we have N=3, M=3, and only 3 colors (for simplicity) - R (red), G (green), and B (blue), a random grid might look like this:

R B R
G G B
R B G

Changing 0,0 (which has value R) to G will result in:

G B R
G G B
R B G

Changing 0,0 (which now has value G) to B will result in:

B B R
B B B
R B G

Then to R:

R R R
R R R
R R G

And the last move, to G:

G G G
G G G
G G G

My math skills are decent, but not graduate-level, and I am sure there is some existing complex algorithm out there that can be used. I just have no idea what it is, and might need a nudge in the right direction on how to apply it.

Can anyone lend a hand??

Cheers,

Chris

'Help with DP algorithm' Thread RSS Feed

Help with DP algorithm