连连看大局消除算法

连连看全局消除算法

好久没写技术博客了。Iteye依然这么亲切！

内存分析了连连看内部数据，找出了方块摆放的那一段数据，用程序把它读出来，放到一个二维数组里面，构成一个矩阵。

这些数据就做为这个算法的数据基础。

这是今天突发奇想，写出来的代码，结合内存读出来的数据，可以瞬间把连连看里面的方块消得个精光。

开局：

?

一阵电闪雷鸣，瞬间之后，就变成下面这样子了：

但本篇文章不讲这个外挂程序。只讲里面涉及到的连连看全局算法。

本算法事实上也就是在一般的连连看消除算法上，包装了下。写过连连看游戏的朋友应该都明白怎样判断两个方块是否可以消除，而本算法就是循环地判断全局所有的可消除的方块，一对一对地消掉，直到最后没有方块时才停止程序。

其实说来说去，这个算法的本质也就是深搜。基本思路如下：

从左上角第一格开始，用深搜查找它在两个转弯之内可以碰到的和它一样的方块，如果找到，就消去，把矩阵里面相应的两个数值也设成0。再以第二格为起点，用同样的方法查找和它一样的方块。以此类推，一格一格地，一行一行地遍历整个矩阵。第一遍过去，基本上都有剩下方块。于是进行第二次遍历。那么怎么判断全局的方块都已经消完了？很简单，一开始看一共有多少方块，每消去一对就减2，直到为0时就停止遍历。

思路看起来很简单，但其实限制条件特别多，写起来很可能会有哪一方面没考虑到。于是调了好久。。。

下面就直接给出算法的代码，结合上面的思路，应该很容易看懂：

?

#include <iostream>using namespace std;#define MAX_X 11 //11行#define MAX_Y 19 //19列int m_matrix[MAX_X][MAX_Y] = {0,0x0,0x0,0x18,0xf4,0x0,0x11,0xa,0x12,0x9,0x12,0x3,0x37,0x11,0x5,0x1b,0x1d,0x3,0x0,0x0,0x0,0xe,0x1d,0x0,0x0,0x12,0x0,0xc,0x0,0x4,0xf4,0xa,0xc,0xd,0xf,0x14,0x2,0xf7,0x0,0x0,0x8,0x9,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x1c,0xd,0x0,0x0,0x4,0x0,0x0,0x37,0x0,0x0,0xb,0x14,0x2,0x0,0x0,0x0,0x0,0x0,0x0,0xf3,0x5,0x0,0x0,0xc,0x0,0x0,0xe,0x8,0xf5,0x5,0x0,0x6,0x3,0xf3,0x0,0x0,0x0,0x0,0x1d,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0xf7,0x14,0x0,0x0,0x0,0x0,0x19,0xf,0xb,0x13,0x1a,0x0,0x0,0x14,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x19,0xf5,0x9,0x0,0x0,0x1b,0x1d,0x0,0x0,0x0,0x15,0xd,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x9,0x1c,0x16,0x5,0x16,0x2,0x13,0x17,0x0,0x3,0x0,0xd,0x0,0x0,0x17,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x10,0xc,0x10,0x1a,0x15,0x0,0x6,0x1a,0x2,0x0,0x18,0x1a,0x12,0x0,0x0,0x0};int dir[][2] = {0,1,1,0,0,-1,-1,0};int gx,gy;bool FindTheSame(int &x, int &y, int d0, int turnCnt,bool turn)  //x表示行，y表示列{//d0表示前一步的方向,用来防止它往回走; turnCnt表示转弯的次数，超过两个就不算了，返回//turn表示从上一步到这一步，是否已经转弯了if(turn) turnCnt ++;if(turnCnt > 2) return false;int d = 0;for(; d < 4; d ++){if(d == (d0+2)%4) continue;//其它三个方向没搜索完之前，不让它按原方向返回int newx = x+dir[d][0];int newy = y+dir[d][1];if(newx < 0 || newx > MAX_X-1 || newy < 0 || newy > MAX_Y-1) continue; //越界了if(newx == gx && newy == gy) continue; //找到的是原来的那个if(m_matrix[newx][newy]){if(d0 >= 0 && d != d0) if(turnCnt+1 > 2) continue;if(m_matrix[gx][gy] == m_matrix[newx][newy]){x += dir[d][0];y += dir[d][1]; //返回x,y数值return true;}else{continue;}} else{bool flag = false;if(d0 >= 0 && d != d0) flag = true;if(FindTheSame(newx,newy,d,turnCnt,flag)){x = newx;y = newy;return true;//跳到下一个空格}}}if(turn) turnCnt --;return false;}int main(){int i,j,tmpi,tmpj;int curCnt = 0;//得到目前总块数：for(int i = 0; i < MAX_X; i ++)for(int j = 0; j < MAX_Y; j ++)if(m_matrix[i][j]) curCnt++;curCnt /= 2;while(curCnt){for(i = 0; i < MAX_X; i ++){for(j = 0; j < MAX_Y; j ++){if(!m_matrix[i][j]) continue;tmpi = gx = i;tmpj = gy = j;if(FindTheSame(tmpi,tmpj,-4,0,false)) //-4是为了避免干扰在FindTheSame里面对是否原路返回的判断{//能到这里，说明已经找到一对了，消去m_matrix[i][j] = 0;m_matrix[tmpi][tmpj] = 0;curCnt --;}}}}return 0;}

? 注意，这个算法用于边缘同行或同列上不能消除的情况。如果要改为边缘可消除，那么给数组加一圈0就行了。

?这些代码调了很久，调到最后头都有点晕了，基础不太好。。

有不足或有改进的地方，欢迎大家在评论中指出来，一起学习！