c++ - 解决类似 Flood-It 难题的最少点击次数

Question

我有 N × M 个网格，其中每个单元格都用一种颜色着色。

当玩家点击颜色为 α 的网格中的任何单元格时，网格最左上角的颜色为 β 的单元格会接收到颜色 α，但不仅如此:所有连接到的单元格仅使用颜色 α 或 β 的路径源也接收颜色 α。

单元格之间的连接应该只考虑在水平和垂直方向形成路径。例如，当玩家单击左侧图中突出显示的单元格时，网格会接收右侧图形的颜色。游戏的目标是使网格成为单色。

输入描述

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.

输出描述

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.

输入样本

1:

4 5
01234
34567
67890
90123

2:

4 5
01234
12345
23456
34567

3:

4 5
00162
30295
45033
01837

输出样本

1:

12

2:

7

3:

10

我正在尝试通过回溯找到解决方案(因为 8 秒的时间限制和小尺寸的网格)。但它正在超过时间限制。有些人只用了 0 秒就成功了。

还有其他算法可以解决这个问题吗？

#include <stdio.h>
#include <string.h>

#define MAX 5
#define INF 999999999

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(signed_integer 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;
}

void backtrack(signed_integer 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;

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

    //this solution is equals to another ? ... getting back
    if (cont == _cont)
        return;

    ++k;//new click

    //copy this matrix and backtrack
    signed_integer copy[MAX][MAX];
    for (signed_integer c = 0; c < 10; ++c){
        if (colors[c] && c != cur_grid[0][0]) {
            memcpy(copy, cur_grid,n*m*sizeof(signed_integer));
            backtrack(copy,k,cont,c);
        }
    }
}

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

int main(void) {
    signed_integer 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() - '0';
        }
    }
    mink = INF;
    backtrack(grid,0, 0, grid[0][0]);
    printf("%d\n",mink);
    return 0;
}

Answer 1

高水平改进

请注意，单元格要么是它们的原始颜色，要么是最后选择的颜色。

这意味着我们可以通过 20 位(标记每个 4*5 单元格是否包含原始颜色)和 0 到 9 范围内的数字来表示棋盘的当前状态选择的颜色。

这样最多可以探索 1000 万个州。如果回溯函数到达已经访问过的状态，则可以避免递归。我希望此更改会使您的解决方案更快。

低级改进

用 20 位掩码和最后一种颜色表示状态也使状态更新和恢复更快，因为只需要更改 2 个数字而不是整个板的 memcpy。