Coloring grid game

I have grid N × M in which each cell is coloured with one colour.

When the player clicks on any cell of the grid of colour α, the cell in the top-leftmost corner of the grid, 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 connection 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.

Input Description


The first line of the input consists of 2 integers N and M (1 ≤ N ≤ 4, 1 ≤ M ≤ 5), which represent respectively the number of lines and the number of columns of the grid. The N lines following describe the initial configuration of the grid, representing each colour by an integer between 0 and 9. The input does not consist of any other line.

Output Description


Print a line containing a single integer that represents the minimum number of clicks that the player must do in order to make the grid monochromatic.

Input Sample


1:



4 5

01234

34567

67890

90123



2:



4 5

01234

12345

23456

34567



3:



4 5

00162

30295

45033

01837


Output Sample


1:



12



2:



7



3:



10


I'm trying to find a solution with backtracking (Because of the time limit of 8 seconds and small size of the grid). But it is taking time limit exceeded. How can i make it faster ?

```
#include
#include
#include

#define MAX 5
#define INF 999999999

char original_grid[MAX][MAX];

typedef int signed_integer;

signed_integer n,m,mink;
bool vst[MAX][MAX];

signed_integer flood_path[4][2] = {
{-1,0},
{1,0},
{0,1},
{0,-1}
};

//flood and paint all

This is not C++. This is C. I suspect the only reason you label it as C++ code is because you needed to use a map.

-
Don't use C-style headers. ` instead of . Don't use , use .

-
Macros are bad. They give horrible error messages, don't follow scoping rules, and confuse the reader.

a. What can MAX mean? What does INF mean? The casual observer will assume that these might refer to a max function and the IEEE infinity respectively, but they don't.

-
Why signed_integer? Why not just int? It increases the verbosity of your program and confuses the reader.

-
Terrible variable names. n, m, mink and vst convey zero meaning.

-
Don't use memset. Don't use memcpy, use std::copy. What if your types change, say instead of an array you now have a vector? Suddenly refactoring.

-
Speaking of which, don't use raw arrays, use a vector.

-
vst_states is used nowhere in your program. It's commented out. It's discouraged to have commented out (dead) code, so remove it. Let VCS do the job.

-
Is cleanBuffer() a good function name? Considering you have a program that deals with filling and painting it's ambiguous. Actually, getchar_unlocked` is non-standard and shouldn't be used at all.

StackExchange Code Review Q#105723, answer score: 7