Coloring grid game

Question

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 <stdio.h>
#include <string.h>
#include <unordered_map>

#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 possible cells... the root is (i,j)
signed_integer flood_and_paint(char cur_grid[MAX][MAX],signed_integer i, signed_integer j, signed_integer beta, signed_integer alpha, signed_integer colors[]){
    //invalid cell
    if (vst[i][j] || i < 0 || i >= n || j < 0 || j >= m)
        return 0;

    //mark existent colors
    colors[cur_grid[i][j]] = 1;

    //only alpha and beta colors counts
    if (cur_grid[i][j] != beta && cur_grid[i][j] != alpha)
        return 0;

    //mark (i,j) as visited and change its color
    vst[i][j] = true;
    cur_grid[i][j] = alpha;

    //floodit !
    signed_integer ret = 1;
    for (signed_integer k = 0; k < 4; k++)
        ret += flood_and_paint(cur_grid,i + flood_path[k][0], j + flood_path[k][1], beta, alpha, colors);

    //how many cells change
    return ret;
}

std::unordered_map<int,std::unordered_map<int,bool> > vst_states;
void backtrack(char cur_grid[MAX][MAX],signed_integer k,signed_integer _cont, signed_integer alpha) {
    //bigger number of clicks for this solution ? ... getting back
    if(k >= mink)
        return;

    signed_integer colors[10];
    memset(vst, false, sizeof(vst));
    memset(colors, 0, sizeof(colors));

    signed_integer beta = cur_grid[0][0];
    signed_integer cont = flood_and_paint(cur_grid, 0, 0, beta, alpha, colors);

    //there are alpha colors to change and no beta colors to change
    colors[alpha] = 1;
    colors[beta]  = 0;
    colors[cur_grid[0][0]] = 0; //there is no need to visit a color equals to grid[0][0]

    //all squares on same color
    if (cont == n * m) {
        mink = k;
        return;
    }

    ++k;//new click

    //get the state of this solution... the cells are either their original colour, or the last selected colour.
    //so we can represent the state with a 20 bit mask and the last color selected(alpha) ... this was a hint given to me ...cant get this solution to work on T.T
    /*
    int state = 0;
    for (int i = 0,st = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            state |= ((cur_grid[i][j] == original_grid[i][j])<<st);
            ++st;
        }
    }
    vst_states[state][alpha] = true;
    */

    //visit all possible colors
    char copy[MAX][MAX];
    for (signed_integer c = 0; c < 10; ++c){
        if (colors[c] /*&& !vst_states[state][c]*/  ) {
            memcpy(copy, cur_grid,n*m*sizeof(char));
            backtrack(copy,k,cont,c);
        }
    }
}

void cleanBuffer(){
    while (getchar_unlocked() != '\n');
}

int main(void) {
    char grid[MAX][MAX];
    scanf("%d %d",&n,&m);
    for (signed_integer i = 0; i < n; ++i) {
        cleanBuffer();
        for (signed_integer j = 0; j < m; ++j){
            grid[i][j] = getchar_unlocked() - '0';
        }
    }
    memcpy(original_grid, grid,n*m*sizeof(char));
    mink = INF;
    backtrack(grid,0, 0, grid[0][0]);
    printf("%d\n",mink);
    return 0;
}

Answer 1

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.

1. Don't use C-style headers. <cstdio> instead of <stdio.h>. Don't use <cstdio>, use <iostream>.

2. 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.

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

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

5. 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.

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

7. 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.

8. 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.

Answer 2

Types and Variables and Functions, oh my!

Let's start with this. There's a lot of choices you made in your solution that makes it difficult to code and more difficult to read. Your grid representation is:

#define MAX 5
char grid[MAX][MAX];

Macros and raw arrays are like the bastard stepchildren of C++. They kind of work, but they're basically broken and are much harder to use than they need to be. It's hard to iterate over a raw array, it's hard to copy a raw array, and MAX is an insufficient name for this constant. Strongly prefer:

static const int GRID_DIM = 5;
using Grid = std::array<std::array<int, 5>, 5>;
Grid grid;

Now we're safer and our Grid is copyable! We will take advantage of this fact.

Also, you rely on a lot of global variables:

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

This makes your algorithm very difficult to understand as you keep referencing external variables to it. I barely know what any of these are for. Definitely signed_integer is an unnecessary typedef (since int is clearly signed already), and it's an interesting contrast in the verbosity for signed_int and your k, which is apparently the number of steps you've taken thus far.

The reliance on globals makes your code structure odd too. The problem is: find the minimum number of steps to make a monochromatic grid. That is crying out for this signature:

int min_steps(Grid );

But instead you set a global variable. That makes it hard to understand.

Also, your most important helper function has this signature:

signed_integer flood_and_paint(char cur_grid[MAX][MAX],signed_integer i, signed_integer j, signed_integer beta, signed_integer alpha, signed_integer colors[]);

SIX arguments! That's a lot of arguments. But conceptually, we're painting the grid based on a single selection, so shouldn't there be just two arguments? What are all the others for? What is the return type? It's difficult to understand this function.

The Algorithm

You are using depth-first search. But we want the minimum number of steps, which calls for breadth-first search. Because you picked the wrong algorithm to start with, you are doing far more searching than is strictly necessary. Furthermore, we can even use A* with a simple heuristic (# of colors remaining) as a future optimization exercise. This switch will save you a huge amount of time, but in order to do that, we have to structure your code into bite-size units. This is a job for...

Functional Programming

Let's get back to key principles. We have a Grid. We need to do one of three things to it. We need to know if it's monochrome. We need to know what colors are left in it. We need to paint a color. That calls for three functions that do three different things:

bool is_monochrome(Grid const& grid)
{
    for (auto& row : grid) {
        for (char val : row) {
            if (val != grid[0][0]) {
                return false;
            }
        }
    }
    return true;
}

When you separate out your concerns, that function above is easy to understand. You are checking if you're done based on the return value of your flood function which is named cont?

We also need the list of available colors:

std::set<char> available_colors(Grid const& grid) {
    std::set<char> colors;

    for (auto& row : grid) {
        for (char val : row) {
            colors.insert(val);
        }
    }

    return colors;
}

I'll leave paint as an exercise to the reader, but note that it needs to follow this signature and should not use any global variables:

Grid paint(Grid const& orig, char alpha);

Once we have those simple building blocks, putting them together to write breadth-first search is downright pleasant:

// save a grid along with the # of steps we took to get here
struct QueueItem {
    int steps;
    Grid grid;
};

// QueueItems compare only as a function of the number of steps, for
// priority_queue we want the smallest first, so we use > on steps
struct QueueItemCompare {
    bool operator()(const QueueItem& lhs, const QueueItem& rhs) const
    {
        // TODO: for A*, additionally add some heuristic on Grid
        return lhs.steps > rhs.steps;
    }
};

int min_steps(Grid const& grid)
{
    std::priority_queue<QueueItem, 
                        std::vector<QueueItem>, 
                        QueueItemCompare> q;

    // to start with, zero-steps and our current grid
    q.push({0, grid});

    while (!q.empty()) {
        QueueItem next = q.top();
        q.pop();

        if (is_monochrome(next.grid)) {
            // breadth-first search, so the first solution
            // we find is the minimum solution
            return next.steps;
        }

        // push all of the next possible steps
        for (char alpha : available_colors(next.grid)) {
            q.push({next.steps + 1,
                    paint(next.grid, alpha)});
        }
    }
}

When we put the grid as a copyable object, we get the very nice property that we can now return Grids from functions (since you cannot return a raw array for a function). That makes it so that we can just write this step:

q.push({next.steps + 1,
        paint(next.grid, alpha)});

That's most of the work right there - for each available color, pick one, increment the step count, and get a new grid. The nice thing is that now our entire actual algorithm is self-contained, no global variables, is just 26-lines of code including whitespace and comments.

Answer 3

Solution by Peter de rivaz:

Note that the cells are either their original colour, or the last selected colour.

This means that we can represent the current state of the board by means of 20 bits (marking for each of the 4*5 cells whether they contain the original colour), and a number in the range 0 to 9 giving the last colour chosen.

This results in a maximum of 10 million states to explore. The backtracking function can avoid having to recurse if it reaches a state that has already been visited. I would expect this change to make your solution considerably faster.