c – 解决洪水般的难题的最小点击次数

概述我有网格N×M,其中每个单元格都用一种颜色着色. 当玩家点击颜色α的网格的任何单元格时,网格的顶部左上角的单元格β,接收颜色α,但不仅如此：所有这些通过连接到源的单元格仅使用颜色α或β的路径也接收颜色α. 单元格之间的连接应仅在水平和垂直方向上考虑以形成路径.例如,当玩家点击左侧图中突出显示的单元格时,网格会接收图形向右的着色.游戏的目标是使网格单色. 输入说明 The first line of 我有网格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 mono@R_876_4048@.

输入样品

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 999999999typedef int signed_integer;signed_integer n,m,mink;bool vst[MAX][MAX];signed_integer flood_path[4][2] = {    {-1,0},{1,{0,1},-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,sizeof(colors));    signed_integer beta = cur_grID[0][0];    signed_integer cont = flood_and_paint(cur_grID,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,grID[0][0]);    printf("%d\n",mink);    return 0;}

解决方法 高水平的改善

请注意,单元格是其原始颜色或最后选定的颜色.

这意味着我们可以用20位表示电路板的当前状态(4 * 5单元中的每个单元的标记是否包含原始颜色)以及范围为0到9的数字,给出最后选择的颜色.

这导致最多可以探索1000万个州.回溯功能可以避免如果达到已经访问的状态,则必须进行递归.我希望这个更改能够使您的解决方案更快.

水平提高

通过20bit掩码表示状态,最后一种颜色也使得状态更快更新,因为只需要更改2个数字,而不是全板的memcpy.

总结

以上是内存溢出为你收集整理的c – 解决洪水般的难题的最小点击次数全部内容，希望文章能够帮你解决c – 解决洪水般的难题的最小点击次数所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。