连连看全局消除算法

好久没写技术博客了。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就行了。

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

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

评论

2 楼 在世界的中心呼喚愛 2014-12-15  

思路很好

1 楼 蛋呢823 2012-03-09  

嗯，太暴力。 哈哈