三消算法

起因

大一上学期的C语言大作业我们编写了一个消消乐游戏，示例视频如下

效果不错，但代码惨不忍睹，尤其是消去判断部分(游戏主体逻辑)。
今天我在这里回顾一下编写的经历及一些改进。

编写代码的过程

构造了一个7行8列的数组存放数字0-5，其中，0代表的是被消去的状态，1-5分别对应着5种图案
而消去判断函数的作用就是接受这个数组，并判断此时是否有可以消去的地方
将其置为0，然后使0上方的图案下降，最上面的随机生成新图案
返回是否可以消去(true/false)，并记录下本次消去的数目(作为分数)
重复调用这个函数，直到返回值为0，即不再有可以消去的地方，就完成了一次排查
我最开始写的代码如下

bool judgemove(int a[][8], int *score)
{
    judge = 0;
    for (i = 1; i < 6; i++)
        for (j = 0; j < 8; j++)
        {
            if (a[i][j] != 0&&a[i][j] == a[i - 1][j] && a[i][j] == a[i + 1][j])//逐列寻找
            {
                for (m = i - 1; m <= i + 1; m++)
                {
                    a[m][j] = 0;//找到了三个相连，就将其置为0
                    setpicture(m, j, a[m][j]);//打印消去状态(黑色方块)
                }
                judge = 1;//确实消去了
            }
        }
    for (i = 0; i < 7; i++)//同上，但是逐行寻找
        for (j = 1; j < 7; j++)
        {
            if (a[i][j] != 0 && a[i][j] == a[i][j - 1] && a[i][j] == a[i][j + 1])
            {
                for (m = j - 1; m <= j + 1; m++)
                {
                    a[i][m] = 0;
                    setpicture(i, m, a[i][m]);
                }
                judge = 1;
            }
        }
    Sleep(200);//停顿以显示哪些被消去了
    for (j = 0; j < 8; j++)
        for (i = 6; i >= 0; i--)//逐列从下向上遍历，实现移动
            while (a[i][j] == 0)
            {
                for (m = i; m > 0; m--)
                    a[m][j] = a[m - 1][j];
                if (m == 0)//如果到达最上面，最上面的变成随机颜色
                    a[m][j] = random_picture();
            }
    for (i = 0; i < 7; i++)//重新打印
        for (j = 0; j < 8; j++)
            setpicture(i, j, a[i][j]);
    return judge;
}

这段代码的不足是明显的，即仅仅判断了连续三个消除的情况，对于连续四个或五个，只会消去前三个
同时，对于T字形，由于纵向遍历在前，只会消除一竖排，而横排不会被消去
这都是很明显的错误
基于此，不断尝试，修修补补，终于把所有情况都写进来了，得到如下代码

bool judgemove(int a[][8],int version ,int *score)//version代表不同位置使用的判断（是否掉落与替换）
{
    static int judge1=1, judge2=0, judge3=0, i, j, m, n,p,q;
    int countx = 0, county = 0;//countx,county用来判断一次消去的个数（有没有五连消）
    if(version==1)
        Sleep(200);//暂停来调试
    judge1 = 0;//judge1用来判断还有没有待消去的棋子
    //如果出现了可以消去的棋子，先赋成零（形象化变为白色）
    for (i = 0; i < 7; i++)//遍历方向是从上到下，一竖列一竖列遍历
        for (j = 0; j < 8; j++)
        {
            judge2 = 0;
            for (m = i + 1; m<=5 && a[i][j] != 0 && a[m][j] == a[i][j] && a[m + 1][j] == a[i][j]; m++)
            //从小到大遍历，m<=5是因为最多纵向遍历到倒数第三行
            //利用了逻辑运算符的短路特性，最后一个相同点要在循环外面赋值
            {
                if (a[m][j - 1] == a[m][j] && a[m][j + 1] == a[m][j]&&j<7&&j>0)//t字形
                {
                    if (a[m][j + 2] == a[m][j])
                        a[m][j + 2] = 0;
                    if (a[m][j - 2] == a[m][j])
                        a[m][j - 2] = 0;
                    if ((!a[m][j + 2]) && (!a[m][j - 2]))//形成炸弹
                        bomb++;
                    a[m][j - 1] = 0;
                    a[m][j + 1] = 0;
                }
                judge3 = 0;
                for (n = j - 1; n > 0 && a[m][j] != 0 && a[m][n] == a[m][j] && a[m][n - 1] == a[m][j]; n--)//反向探索
                //每消去一个棋子前，都要看看它的横向能不能消去
                {
                    a[m][n] = 0;
                    judge3 = 1;
                    countx++;
                }
                if (judge3&&n>=0&&n<8)
                    a[m][n] = 0;
                judge3 = 0;
                for (n = j + 1; j < 6 && a[m][j] != 0 && a[m][n] == a[m][j] && a[m][n + 1] == a[m][j]; n++)//正向探索
                {
                    a[m][n] = 0;
                    judge3 = 1;
                    countx++;
                }
                if (judge3 && n < 8 && n >= 0)
                {
                    a[m][n] = 0;
                    countx++;
                    if (countx >= 5)
                        bomb++;
                    countx = 0;
                }
                a[m][j] = 0;
                county++;
                judge2 = 1;
                judge1 = 1;
            }
            if (judge2 == 1)//judge2=1代表纵向消去，为最后一个相同点单独赋值
            {
                if (a[m][j - 1] == a[m][j] && a[m][j + 1] == a[m][j]&&j<7&&j>0)//t字形
                {
                    if (a[m][j + 2] == a[m][j])
                        a[m][j + 2] = 0;
                    if (a[m][j - 2] == a[m][j])
                        a[m][j - 2] = 0;
                    if ((!a[m][j + 2]) && (!a[m][j - 2]))//形成炸弹
                        bomb++;
                    a[m][j - 1] = 0;
                    a[m][j + 1] = 0;
                }
                judge3 = 0;
                for (n = j - 1; n > 0 && a[m][j] != 0 && a[m][n] == a[m][j] && a[m][n - 1] == a[m][j]; n--)//反向探索
                {
                    a[m][n] = 0;
                    judge3 = 1;
                    countx++;
                }
                if (judge3&&n>=0&&n<8)
                    a[m][n] = 0;
                judge3 = 0;
                for (n = j + 1; j < 6 && a[m][j] != 0 && a[m][n] == a[m][j] && a[m][n + 1] == a[m][j]; n++)//正向探索
                {
                    a[m][n] = 0;
                    judge3 = 1;
                    countx++;
                }
                if (judge3&&n<8&&n>=0)
                {
                    a[m][n] = 0;
                    countx++;
                    if (countx >= 5)
                        bomb++;
                    countx = 0;
                }
                a[m][j] = 0;
                county+=2;
                if (county >= 5)
                    bomb++;
                county = 0;
            }
            for (n = j + 1; n <= 6 && a[i][j] != 0 && a[i][n] == a[i][j] && a[i][n + 1] == a[i][j]; n++)
                //n<=6是因为最多横向遍历到倒数第三列，逻辑运算符利用了短路特性
            {
                judge3 = 0;
                for (m = i - 1; m>1 && a[i][n] != 0 && a[m][n] == a[i][n] && a[m - 1][n] == a[i][n]; m--)//反向探索
                {
                    a[m][n] = 0;
                    judge3 = 1;
                    county++;
                }
                if (judge3&&m>=0&&n<8)
                    a[m][n] = 0;
                judge3 = 0;
                for (m = i + 1; i < 5 && a[i][n] != 0 && a[m][n] == a[i][n] && a[m + 1][n] == a[i][n]; m++)//正向探索
                {
                    a[m][n] = 0;
                    judge3 = 1;
                    county++;
                }
                if (judge3 && m < 7 && n < 8)
                {
                    a[m][n] = 0;
                    county++;
                    if (county >= 5)
                        bomb++;
                    county = 0;
                }
                a[i][n] = 0;
                countx++;
                judge2 = 2;
                judge1 = 1;
            }
            if (judge2 == 2)//judge2=2代表横向消去，为最后一个相同点单独赋值
            {
                judge3 = 0;
                for (m = i - 1; m > 1 && a[i][n] != 0 && a[m][n] == a[i][n] && a[m - 1][n] == a[i][n]; m--)
                {
                    a[m][n] = 0;
                    judge3 = 1;
                    county++;
                }
                if (judge3&&m>=0 && n < 8)
                    a[m][n] = 0;
                judge3 = 0;
                for (m = i + 1; i < 5 && a[i][n] != 0 && a[m][n] == a[i][n] && a[m + 1][n] == a[i][n]; m++)
                {
                    a[m][n] = 0;
                    judge3 = 1;
                    county++;
                }
                if (judge3 && m < 7 && n < 8)
                {
                    a[m][n] = 0;
                    county++;
                    if (county >= 5)
                        bomb++;
                    county = 0;
                }
                a[i][n] = 0;
                countx += 2;
                if (countx >= 5)
                    bomb++;
                countx = 0;
            }
            if (judge2)//只要有消去，就将起始点消去（前面要保留，否则不能判断既横向又纵向的情况）
                a[i][j] = 0;
        }
    if (version != 2&&version!=3)//如果是判断能不能移动或初次进入，不打印	
    {
        for (p = 0; p < 7; p++)//重新打印，显示出黑色矩形
            for (q = 0; q < 8; q++)
            {
                setpicture(p, q, a[p][q]);
                if (a[p][q] == 0)
                    (*score)++;//分数增加
            }
    }
    if (version == 2)
        return judge1;
    if(version==1)
        Sleep(200);
    for (j = 0; j < 8; j++)
        for (i = 6; i >= 0; i--)
            while (a[i][j] == 0)
            {
                for (m = i; m > 0; m--)
                    a[m][j] = a[m - 1][j];
                if (m == 0)//如果到达最上面，最上面的变成随机图像
                    a[m][j] = random_picture();
            }
    if(version==1)
        for (i = 0; i < 7; i++)//重新打印
            for (j = 0; j < 8; j++)
                setpicture(i, j, a[i][j]);
    return judge1;
}

实在太长了，我自己都懒得看，而且有太多重复的部分
值得一提的是，该函数又引入了一个参数version
version代表该函数被调用的位置
version1:游戏过程中，正常地判断，返回，消去，打印
version2:反馈给鼠标控制函数移动是否合法，只需要是否能消去这个结果(true/false)
version3:刚进入游戏，此时不会把中间过程打印在屏幕上
并且会记录每次消去的个数，到达五个会给予奖励
这个函数成功地实现了所需的功能，并作为了提交版本
而今天再看时，发现如此复杂的原因是每次都是找到时就将它们置零
这就代表当时就要考虑所有情况，十分麻烦
今天我做了修改，仅仅将要消去的元素记录下来，到最后再一并消去
代码如下

bool judgemove(int a[][8], int version, int* score)//version代表不同位置使用的判断（是否掉落与替换）
{
    static int judge1 = 1, judge2 = 0, i, j, m, n, p, q;
    int countx = 0, county = 0;//countx,county用来判断一次消去的个数（有没有五连消）
    int count, change[2][100], t=0;//change数组记录下要消去的坐标，第一行记录行数，第二行记录列数
    if (version == 1)
        Sleep(200);//暂停来调试
    judge1 = 0;//judge1用来判断还有没有待消去的棋子
    //如果出现了可以消去的棋子，先赋成零（形象化变为白色）
    for (i = 0; i < 7; i++)//遍历方向是从上到下，一竖列一竖列遍历
        for (j = 0; j < 8; j++)
        {
            judge2 = 0;
            for (m = i + 1; m <= 5 && a[i][j] != 0 && a[m][j] == a[i][j] && a[m + 1][j] == a[i][j]; m++)
            //从小到大遍历，m<=5是因为最多纵向遍历到倒数第三行
            //利用了逻辑运算符的短路特性，最后一个相同点要在循环外面赋值
            {
                change[0][t] = m;
                change[1][t] = j;
                ++t;
                ++county;
                judge2 = 1;
                judge1 = 1;
            }
            if (judge2 == 1)//judge2=1代表纵向消去，为最后一个相同点单独赋值
            {
                change[0][t] = m;
                change[1][t] = j;
                ++t;
                county += 2;
                if (county >= 5)
                    bomb++;
                county = 0;
            }
            for (n = j + 1; n <= 6 && a[i][j] != 0 && a[i][n] == a[i][j] && a[i][n + 1] == a[i][j]; n++)
                //n<=6是因为最多横向遍历到倒数第三列，逻辑运算符利用了短路特性
            {
                change[0][t] = i;
                change[1][t] = n;
                ++t;
                ++countx;
                judge2 = 2;
                judge1 = 1;
            }
            if (judge2 == 2)//judge2=2代表横向消去，为最后一个相同点单独赋值
            {
                
                change[0][t] = i;
                change[1][t] = n;
                ++t;
                countx += 2;
                if (countx >= 5)
                    bomb++;
                countx = 0;
            }
            if (judge2)//只要有消去，就将起始点消去
                a[i][j] = 0;
        }
    for (i = 0; i < t; ++i)
        a[change[0][i]][change[1][i]] = 0;
    if (version != 2 && version != 3)//如果是判断能不能移动或初次进入，不打印	
    {
        for (p = 0; p < 7; p++)//重新打印，显示出黑色矩形
            for (q = 0; q < 8; q++)
            {
                setpicture(p, q, a[p][q]);
                if (a[p][q] == 0)
                    (*score)++;//分数增加
            }
    }
    if (version == 2)
        return judge1;
    if (version == 1)
        Sleep(200);
    for (j = 0; j < 8; j++)
        for (i = 6; i >= 0; i--)
            while (a[i][j] == 0)
            {
                for (m = i; m > 0; m--)
                    a[m][j] = a[m - 1][j];
                if (m == 0)//如果到达最上面，最上面的变成随机图像
                    a[m][j] = random_picture();
            }
    if (version == 1)
        for (i = 0; i < 7; i++)//重新打印
            for (j = 0; j < 8; j++)
                setpicture(i, j, a[i][j]);
    return judge1;
}