Help with DP algorithm - Programmers Heaven

#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

#### Categories

Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

# Help with DP algorithm

Posts: 1Member
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