The Half-Blood Prince

This year, instead of submit themselves to humbling initiation rituals, the freshmen of the Computer Science undergraduate course have chosen to do something more humanitarian to celebrate their entry into a federal university. First, they have gone to donate blood at HEMOSC, the blood centre of the state of Santa Catarina. Then, still with half of the blood in the body, they have gone to a public school, the Little Prince Municipal Centre of Childhood Education (or just Little Prince), in order to do voluntary works. In one of the developed activities, the children of the school should play a very interesting single-player computer game named Flood It!.

In Flood It!, it is presented to the player a grid N × M in which each cell is coloured with one colour, as in the figure to the left. When the player clicks on any cell of the grid of colour α, the cell in the top-leftmost corner of the grid, called source, of colour β, receives the colour α, but not only it: all those cells which are connected to the source by paths which use only the colours α or β also receive the colour α. The adjacencies between cells should be considered only in the horizontal and vertical directions to form the paths. For example, when the player clicks on the cell highlighted in the figure to the left, the grid receives the colouring of the figure to the right. The goal of the game is to make the grid monochromatic.