解决Flood-It类谜题所需的最少点击次数

Question

我有一个N×M的网格，每个单元格都被染上了一种颜色。

当玩家点击网格中任何一个颜色为α的单元格时，位于网格左上角且颜色为β的单元格将接收颜色α，但不仅如此：所有通过只使用颜色α或β的路径与源相连的单元格也将接收颜色α。

连接单元格应仅考虑水平和垂直方向以形成路径。例如，当玩家单击左侧图中突出显示的单元格时，网格将获得右侧图中的着色。游戏的目标是使网格单色。

输入描述

输入的第一行包括2个整数N和M（1 ≤ N ≤ 4，1 ≤ M ≤ 5），分别表示网格的行数和列数。接下来的N行描述了网格的初始配置，用0到9之间的整数表示每种颜色。输入不包含任何其他行。

输出描述

打印一行包含单个整数的内容，该整数表示玩家必须点击的最小次数，以使网格单色。

示例输入

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

- Felipe

---

你的回溯函数中应该可以消除 memset 调用。同样也可以在每个递归调用之前消除 memcpy。 - IVlad

我编写了一个JavaScript实现我的最优策略，以强制自己明确规则，因为我认为我的答案还有点模糊。该代码成功解决了三个示例，分别进行了38次、1次和4次递归，并且总执行时间只有几毫秒。然而，它相当复杂，所以我不认为我能够在面试期间实现每一个想法。但是单独应用第3条规则可能会使你在时限内完成。 - m69 ''snarky and unwelcoming''

显然，这是基于游戏“Flood It”的，但是在示例中单击2还会连接2下面的0的规则不同。也许你应该把标题改成类似“解决像Flood-It一样的谜题所需的最少点击次数”，这样人们就可以更容易地找到你的问题了？ - m69 ''snarky and unwelcoming''

Answer 1

高级改进

请注意，单元格要么是其原始颜色，要么是上次选择的颜色。

这意味着我们可以通过 20 个位（为每个 4*5 单元格标记它们是否包含原始颜色）和范围在 0 到 9 的数字表示板的当前状态，最多有 1000 万种状态需要探索。如果回溯函数到达已经访问过的状态，则可以避免递归。我期望这个更改会使您的解决方案速度更快。

低级改进

通过 20 位掩码和最后的颜色来表示状态也使得状态更新和恢复变得更加快速，因为只需要更改 2 个数字，而不是整个板的memcpy。

- Peter de Rivaz

---

我还会尝试在每个节点都是矩阵的图上使用A*算法。例如，您可以从左侧图片到右侧图片建立一条边。对于启发式算法，请使用剩余不同颜色的数量-1。我认为这应该有助于修剪很多可能性，并且在第一次思考时是可接受的。 - IVlad

一个可能更好的启发式方法：不属于包含左上角单元格的簇的单元格数量。这将导致在下一步中点击示例中的白色单元格，而先前的启发式方法将允许多个选项，例如蓝色或粉色单元格。然后它会点击5，然后任何顺序都可以。这提供了示例的正确答案为10，但对于更大的示例可能是不可接受的。也许可以使用单元格簇来解决问题。这个想法是为了尽可能地转换尽可能多的单元格。也许其他人可以完成这个想法。 - IVlad

@IVlad 我认为诀窍在于将游戏看作是“9种颜色可点击”而不是“19个方块可点击”。这大大减少了组合的数量。 - m69 ''snarky and unwelcoming''

Answer 2

如果您将4x5棋盘视为“19个可以点击的方格”，那么就意味着有19！或121,645,100,408,832,000种组合需要检查。然而，有许多优化方法可以大幅减少组合数量，仅需几十种即可：

游戏策略观察

• 点击相同颜色的不同方块会产生相同的效果。因此，棋盘应被视为“你可以点击的9种颜色（或更少）”。
• 相邻的相同颜色方块应该被视为一组；它们总是一起作用。在下面的例子中，右下角的三个白色方块就形成了这样一组。
• 只有点击与角落组相邻的颜色才有意义。在下面的例子的第一步中，只有点击粉色、绿色、橙色或白色方块才有意义。
• 当几个唯一着色的组（只有一个组具有某种颜色）与角落组相邻时，它们被点击的顺序并不重要。在下面的例子中，在点击5和3之后，点击4、7、8和9的任何顺序都会产生相同的结果。
• 当所有同一颜色的组都与角落组相邻时，它们可以被视为唯一着色的组；每种颜色只需要单击一次即可将它们连接起来。在下面的例子中，在点击5和3之后，两个粉色方块和两个绿色方块变成了两个唯一着色的组。
• 当棋盘上只有唯一着色的组时，必要的点击次数等于未连接组的数量。在下面的例子中，在点击5和3之后，还需要确切地点击八次。
• 如果只有一个与角落组颜色相同且它们被超过一个其他组隔开的未连接组，则该组可以被视为唯一着色的组。
• 减少点击次数意味着同时连接多个组。这可以通过点击与角落组相邻的几个相同颜色的组（如下面例子中步骤3中的点击1或2），或者通过点击将角落组与具有相同颜色的组分开的组（如下面例子中的步骤1和2）来实现。

基于最优策略的算法

一个基于最优策略的递归算法，根据上述规则进行以下步骤：

1. 如果只剩下唯一颜色的组，点击次数等于未连接组的数量；返回此数字。
2. 如果与角落组相同颜色的组仅被另一个组隔开，点击这个其他组并进行递归。如果有多种选择，请尝试所有选择。
3. 如果一个或多个唯一颜色的组（或所有某些颜色的组）与角落组相邻，请按任意顺序点击它们。然后从步骤1重新评估棋盘。
4. 尝试点击与角落组相邻的每种颜色并进行递归。

JavaScript实现的暴力算法在问题1和3中需要数千万次递归，并且执行时间远高于8秒的限制。在实施上述优化后，问题1只需38次递归即可解决，执行时间为几毫秒。问题2和3甚至更快。

- m69 ''snarky and unwelcoming''