解决Flood-It-like拼图的最少点击数 [英] Minimum number of clicks to solve Flood-It-like puzzle

问题描述

我有网格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 < br>
34567

3：

4 5

00162

30295

45033

01837

输出示例

1：

12

7

p>

10

我试图找到一个解决方案回溯（因为时间限制8秒和网格的小尺寸）。但它是超过时间限制。

有一些其他的算法来解决这个问题。

  #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} 
}; 
 
 //泛洪并绘制所有可能的单元格...根是（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 []）{
 //无效单元格
 if（vst [i] [j] || i <0 || i> = n || j < 0 || j> = m）
 return 0; 
 
 //标记存在的颜色
 colors [cur_grid [i] [j]] = 1; 
 
 //只有alpha和beta颜色计数
 if（cur_grid [i] [j]！= beta& cur_grid [i] [j]！= alpha）
 return 0; 
 
 //标记（i，j）为已访问并更改其颜色
 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] ，alpha，colors）; 
 
 //有多少单元格改变
 return ret; 
} 
 
 void backtrack（signed_integer cur_grid [MAX] [MAX]，signed_integer k，signed_integer _cont，signed_integer alpha）{
 //此解决方案的更多点击次数...回到
 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）; 
 
 //有改变的alpha颜色，没有beta颜色改变
颜色α= 1; 
 colorsβ= 0; 
 
 //相同颜色的所有正方形
 if（cont == n * m）{
 mink = k; 
 return; 
} 
 
 //这个解决方案等于另一个？ ...回到
 if（cont == _cont）
 return; 
 
 ++ k; //新点击
 
 //复制此矩阵和回溯
 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（）！='\\\
'）; 
} 
 
 int main（void）{
 signed_integer grid [MAX] [MAX]; 
 scanf（％d％d，& n，& m）; 
 for（signed_integer i = 0; i  cleanBuffer（）; 
 for（signed_integer j = 0; j  grid [i] [j] = getchar（） - '0' 
} 
} 
 mink = INF; 
 backtrack（grid，0，0，grid [0] [0]）; 
 printf（％d\\\
，mink）; 
 return 0; 
} 
  

解决方案

高级改进

请注意，单元格是其原始颜色或最后选择的颜色。

这意味着我们可以表示通过20位（对于4 * 5个单元中的每一个，标记它们是否包含原始颜色）的板的当前状态，以及在0到9范围内的数字，给出最后选择的颜色。

这将导致最多探索1000万个状态。如果它到达已经访问的状态，则回溯功能可以避免必须递归。我希望这种变化使您的解决方案更快。

低级改进

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

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. Some people just made it on 0 secs.

There is some other algorithm to solve this ?

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

解决方案

High level improvement

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.

Low level improvement

Representing the state by a 20bit mask and the last colour also makes the state a lot quicker to update and restore as only 2 numbers need to be changed instead of memcpy of the whole board.

这篇关于解决Flood-It-like拼图的最少点击数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！