解决类似 Flood-It 难题的最少点击次数
Minimum number of clicks to solve Flood-It-like puzzle
我有 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;
}
高水平改进
请注意，单元格要么是它们的原始颜色，要么是最后选择的颜色。
这意味着我们可以通过 20 位（标记每个 4*5 单元格是否包含原始颜色）和 0 到 9 范围内的数字来表示板的当前状态最后选择的颜色。
这样最多可以探索 1000 万个州。如果回溯函数到达已经访问过的状态，则可以避免递归。我希望此更改会使您的解决方案更快。
低级改进
用 20 位掩码和最后一种颜色表示状态也使状态更新和恢复更快，因为只需要更改 2 个数字而不是整个板的 memcpy。
如果您将 4x5 棋盘想象成“可以点击的 19 个方块”，那就意味着有 19 个！或 121,645,100,408,832,000 种组合进行检查。然而，有许多优化可以将组合的数量大幅减少到只有几十个：
对游戏攻略的观察
- 点击相同颜色的不同方块效果相同。所以棋盘应该被视为“你可以点击的 9 种颜色（或更少）”。
- 颜色相同的相邻方块应视为一组；他们总是一起行动。在下面的例子中，右下角的三个白色方块就是这样一组。
- 只有点击与角组相邻的颜色才有意义。在下面示例的第一步中，只有点击粉色、绿色、橙色或白色方块才有意义。
- 当几个具有独特颜色的组（其中只有一个组具有特定颜色）与角组相邻时，单击它们的顺序并不重要。在下面的例子中，点击5和3之后，任意顺序点击4、7、8和9都会得到相同的结果。
- 当某种颜色的所有组都与角组相邻时，可以看作是唯一颜色组；每种颜色只需单击一次即可连接它们。在下面的例子中，点击5和3后，两个粉色方块和两个绿色方块变成了两个颜色独特的组
- 当棋盘只有唯一颜色的组时，必要的点击次数等于未连接组的数量。在下面的示例中，在单击 5 和 3 之后，还需要再单击 8 次。
- 如果恰好有一个未连接的组与角组的颜色相同，并且它们被多个其他组分开，则该组可以看作是一个唯一颜色的组。
- 减少点击次数意味着一次连接多个组。这可以在几个相同颜色的组与角组相邻时完成（如在下面示例的步骤 3 中单击 1 或 2 时），或者通过单击将角组与具有相同颜色的组分开的组（正如示例中的步骤 1 和 2 中发生的那样）。
基于最优策略的算法
基于使用上面列出的规则的最佳策略的递归算法，每次递归都要经过这些步骤：
- If only uniquely-coloured groups are left, the number of clicks equals the number of unconnected groups; return this number.
- If a group with the same colour as the corner-group is separated from it by only one other group, click this other group and recurse. If several options exist, try all of them.
- If one or more uniquely-coloured groups (or all groups of certain colours) are adjacent to the corner group, click them all in any order. Then re-evaluate the board from step 1.
- Try clicking every colour adjacent to the corner group and recurse.
Javascript 暴力算法的实现需要数千万次递归，例如问题中的示例 1 和 3，执行时间远超过 8 秒的限制。在实施上述优化后，示例 1 仅用 38 次递归 和几毫秒的执行时间就解决了。示例 2 和 3 甚至更快。
我有 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
901232:
4 5
01234
12345
23456
345673:
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;
}
高水平改进
请注意，单元格要么是它们的原始颜色，要么是最后选择的颜色。
这意味着我们可以通过 20 位（标记每个 4*5 单元格是否包含原始颜色）和 0 到 9 范围内的数字来表示板的当前状态最后选择的颜色。
这样最多可以探索 1000 万个州。如果回溯函数到达已经访问过的状态，则可以避免递归。我希望此更改会使您的解决方案更快。
低级改进
用 20 位掩码和最后一种颜色表示状态也使状态更新和恢复更快，因为只需要更改 2 个数字而不是整个板的 memcpy。
如果您将 4x5 棋盘想象成“可以点击的 19 个方块”，那就意味着有 19 个！或 121,645,100,408,832,000 种组合进行检查。然而，有许多优化可以将组合的数量大幅减少到只有几十个：
对游戏攻略的观察
- 点击相同颜色的不同方块效果相同。所以棋盘应该被视为“你可以点击的 9 种颜色（或更少）”。
- 颜色相同的相邻方块应视为一组；他们总是一起行动。在下面的例子中，右下角的三个白色方块就是这样一组。
- 只有点击与角组相邻的颜色才有意义。在下面示例的第一步中，只有点击粉色、绿色、橙色或白色方块才有意义。
- 当几个具有独特颜色的组（其中只有一个组具有特定颜色）与角组相邻时，单击它们的顺序并不重要。在下面的例子中，点击5和3之后，任意顺序点击4、7、8和9都会得到相同的结果。
- 当某种颜色的所有组都与角组相邻时，可以看作是唯一颜色组；每种颜色只需单击一次即可连接它们。在下面的例子中，点击5和3后，两个粉色方块和两个绿色方块变成了两个颜色独特的组
- 当棋盘只有唯一颜色的组时，必要的点击次数等于未连接组的数量。在下面的示例中，在单击 5 和 3 之后，还需要再单击 8 次。
- 如果恰好有一个未连接的组与角组的颜色相同，并且它们被多个其他组分开，则该组可以看作是一个唯一颜色的组。
- 减少点击次数意味着一次连接多个组。这可以在几个相同颜色的组与角组相邻时完成（如在下面示例的步骤 3 中单击 1 或 2 时），或者通过单击将角组与具有相同颜色的组分开的组（正如示例中的步骤 1 和 2 中发生的那样）。
基于最优策略的算法
基于使用上面列出的规则的最佳策略的递归算法，每次递归都要经过这些步骤：
- If only uniquely-coloured groups are left, the number of clicks equals the number of unconnected groups; return this number.
- If a group with the same colour as the corner-group is separated from it by only one other group, click this other group and recurse. If several options exist, try all of them.
- If one or more uniquely-coloured groups (or all groups of certain colours) are adjacent to the corner group, click them all in any order. Then re-evaluate the board from step 1.
- Try clicking every colour adjacent to the corner group and recurse.
Javascript 暴力算法的实现需要数千万次递归，例如问题中的示例 1 和 3，执行时间远超过 8 秒的限制。在实施上述优化后，示例 1 仅用 38 次递归 和几毫秒的执行时间就解决了。示例 2 和 3 甚至更快。