连连看游戏，2点是否可消除算法分析
标 题：连连看游戏，2点是否可消除算法分析
作 者：小quan
时 间：<font color="#10-11-12 16:03:23 链 接：
现在在看郁金香的VC外挂教程，其中对于连连看外挂
在此感谢这位兄弟
提供的下载地址，现在学习中……
言归正传，这个外挂的最难的就是检查2点是不是可以联通的算法，我们就来研究这一点
这个游戏，发现2点之间连接线段数需要满足&&=&3&这个条件
我们先来谈谈3条线段的情况，先假设，棋盘上除了这2点以外全部为空，这2点分别用p1,p2表示，并显示坐标，那么在连接线段数&=&3&的情况下，一共有多少种路径呢？
我们来思考一下，以下是所有路径，如图3：
（路径用绿线表示）可以看到这不是一两种的问题，而是由很多种，其中我用深颜色的线画出了几条有代表性的路径，
仔细的看图就会发现其中有规律可寻，看图4：
我标出了其中比较重要的4个点！~
这4个点分别是p1,p2在坐标轴上的投影，分别用&px1，px2(表示在x轴上的投影)，py1,py2(表示y轴上的投影)&如图5：
先来分析px1,px2可以从图3上清楚的看到，联通路径上的有一部分就是就是线段px1，px2,或者是它的平行线！~
再分析py1，py2&也是一样的道理
我们再来分析一下px1，px2，py1,py2的坐标情况，如果已知p1（x1,y1）,p2（x2,y2）的坐标,那么px1，px2，py1,py2坐标是什么呢？
只要有几何的初步知识就可以知道px1(x1,0)，px2(x2,0)，py1(0,y1),py2(0,y2)
那么分析上面的一大堆对于我们有什么用呢？
答案是肯定有用！~
图中连通的路径由3条线段，有4个点组成，只要判断线段1，2，3，是否都连通，就可以判断2点是否可以连通了!~
实际上分析，每个人都可以分析的头头是道，编程最难的就是怎么样把分析好的数学模型通过编程来实现，分析是不需要考虑很多的细节问题的，而编程实现需要考虑很多的细节问题！~
那这样的话，就需要先写一个判断2点是否可以连通的函数了！~
好了我们下面来实现这个函数：
注：我用的是VC6.0
bool&LineIfConnect(POINT&Point1,&POINT&Point2,&byte&ChessData[10][18])
&&&&/*&功能&&&：检查Point1,Point2是否连通(2点之间连线的数值是不是为NULL,包括这2点自身)
&&&&&*&参数1&&：第1点
&&&&&*&参数2&&：第2点
&&&&&*&对于参数的要求：Point1.x&==&Point2.x&||&Point1.y&==&Point2.y
&&&&&*&参数3&&：检测2点所在的数组(棋盘)
&&&&&*&返回值&：true&表示可以连通，false&表示不可以连通
&&&&int&i;
&&&&if&((Point1.x&==&Point2.x)&&&&(Point1.y&!=&Point2.y))&&&&//&横坐标相同，纵坐标不同
&&&&&&&&if&(Point1.y&&&Point2.y)&&&&//&point1&在&point2&上方
&&&&&&&&&&&&for&(i&=&Point1.y;&i&&=&Point2.y;&i++)&&&&//&for循环检测2点之间的所有元素
&&&&&&&&&&&&&&&&if&(ChessData[i][Point1.x]&!=&NULL)
&&&&&&&&&&&&&&&&&&&&return&
&&&&&&&&else&if&(Point1.y&&&Point2.y)&&&&//&point1&在&point2&下方
&&&&&&&&&&&&for&(i&=&Point2.y;&i&&=&Point1.y;&i++)&&&&//&for循环检测2点之间的所有元素
&&&&&&&&&&&&&&&&if&(ChessData[i][Point1.x]&!=&NULL)
&&&&&&&&&&&&&&&&&&&&return&
&&&&else&if&((Point1.x&!=&Point2.x)&&&&(Point1.y&==&Point2.y))&&&&//&横坐标不同，纵坐标相同
&&&&&&&&if&(Point1.x&&&Point2.x)&&&&//&point1&在&point2&左边
&&&&&&&&&&&&for&(i&=&Point1.x;&i&&=&Point2.x;&i++)
&&&&&&&&&&&&&&&&if&(ChessData[Point1.y][i]&!=&NULL)
&&&&&&&&&&&&&&&&&&&&return&
&&&&&&&&else&if&(Point1.x&&&Point2.x)&&&&//&//&point1&在&point2&右边
&&&&&&&&&&&&for&(i&=&Point2.x;&i&&=&Point1.x;&i++)&&&&//&for循环检测2点之间的所有元素
&&&&&&&&&&&&&&&&if&(ChessData[i][Point1.x]&!=&NULL)
&&&&&&&&&&&&&&&&&&&&return&
&&&&else&if&((Point1.x&==&Point2.x)&&&&(Point1.y&==&Point2.y))&&//&2点为同一点的情况
&&&&&&&&return&
&&&&&&&&return&
&&&&return&
有了上面这个函数，我们就可以真正编写qq连连看中2点是否可以消除了的函数了，代码如下：
bool&DecideChessIfRemove(POINT&Point1,&POINT&Point2,&byte&ChessData[10][18])
&&&&/*&功能&&&：检查Point1,Point2是否可以消除
&&&&&*&参数1&&：第1点
&&&&&*&参数2&&：第2点
&&&&&*&参数3&&：检测2点所在的数组(棋盘)
&&&&&*&返回值&：true&表示可以消除，false&表示不可以消除
&&&&int&x1&=&Point1.x;
&&&&int&y1&=&Point1.y;&&&&&//&Point1&==&(x1,&y1)
&&&&int&x2&=&Point2.x;
&&&&int&y2&=&Point2.y;&&&&&//&Point2&==&(x2,&y2)
&&&&int&i,&j;
&&&&POINT&p1,&p2;
&&&&byte&point1&=&ChessData[Point1.y][Point1.x];
&&&&byte&point2&=&ChessData[Point2.y][Point2.x];
&&&&ChessData[Point1.y][Point1.x]&=&ChessData[Point2.y][Point2.x]&=&NULL;&&&&&&//&2点在数组的位置设为NULL
&&&&p1.y&=&y1;
&&&&p2.y&=&y2;
&&&&for&(i&=&0;&i&&=&18;&i++)&&&//&横坐标在变&下面的两个for循环是关键，线段py1,py2在平移
&&&&&&&&p1.x&=&i;&&&&//&p1&=&(i,&y1)
&&&&&&&&p2.x&=&i;&&&&//&p2&=&(i,&y2)
&&&&&&&&if&(LineIfConnect(p1,&p2,&ChessData))
&&&&&&&&&&&&if&((LineIfConnect(Point1,&p1,&ChessData))&&&&(LineIfConnect(Point2,&p2,&ChessData)))
&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&ChessData[Point1.y][Point1.x]&=&point1;
&&&&&&&&&&&&&&&&ChessData[Point2.y][Point2.x]&=&point2;
&&&&&&&&&&&&&&&&return&
&&&&&&&&&&&&}
&&&&p1.x&=&x1;
&&&&p2.x&=&x2;
&&&&for&(j&=&0;&j&&=10;&j++)&&&&//&纵坐标在变&，&线段px1,px2&在平移
&&&&&&&&p1.y&=&j;&&&//&p1&=&(x1,&j)
&&&&&&&&p2.y&=&j;&&&//&p2&=&(x2,&j)
&&&&&&&&if&(LineIfConnect(p1,&p2,&ChessData))
&&&&&&&&&&&&if&((LineIfConnect(Point1,&p1,&ChessData))&&&&(LineIfConnect(Point2,&p2,&ChessData)))
&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&ChessData[Point1.y][Point1.x]&=&point1;
&&&&&&&&&&&&&&&&ChessData[Point2.y][Point2.x]&=&point2;
&&&&&&&&&&&&&&&&return&
&&&&&&&&&&&&}
&&&&&&&&&&&&&&&&
&&&&ChessData[Point1.y][Point1.x]&=&point1;
&&&&ChessData[Point2.y][Point2.x]&=&point2;
&&&&return&&&&//&没有找到连通的路径
有了前面的一大堆分析，代码中也有注释，
好了函数的编写告一段落，实际上写程序最为艰难就是调试阶段了
来写一个程序测试一下：
#include&&afxwin.h&&&&&&&&&&//&MFC&core&and&standard&components
#include&&afxext.h&&&&&&&&&&//&MFC&extensions
#include&&afxdisp.h&&&&&&&&&//&MFC&Automation&classes
#include&&afxdtctl.h&&&&&&&&&//&MFC&support&for&Internet&Explorer&4&Common&Controls
#include&&afxcmn.h&&&&&&&&&&&&&//&MFC&support&for&Windows&Common&Controls
#include&&stdio.h&
#include&&stdlib.h&
#include&&function.h&
int&main()
&&&&printf(&开始&测试\r\n\n\n&);
&&&&byte&ChessData[10][18];
&&&&int&i,j;
&&&&for&(j&=&0;&j&&=&10;&j++)
&&&&&&&&for&(i&=&0;&i&&=&18;&i++)
&&&&&&&&&&&&ChessData[j][i]&=&rand()%2;
&&&&&&&&&&&&printf(&%2d&&&,ChessData[j][i]);
&&&&&&&&printf(&\r\n&);
&&&&POINT&p1;&&//&p1的位置
&&&&p1.x&=&13;
&&&&p1.y&=&5;
&&&&POINT&p2;&//&p2的位置
&&&&p2.x&=&14;
&&&&p2.y&=&0;
&&&&if&(DecideChessIfRemove(p1,&p2,&ChessData))
&&&&&&&&printf(&2点相连\n\n&);
&&&&&&&&printf(&2点不相连！~\n\n&);
&&&&for&(j&=&0;&j&&=&10;&j++)
&&&&&&&&for&(i&=&0;&i&&=&18;&i++)
&&&&&&&&&&&&printf(&%2d&&&,ChessData[j][i]);
&&&&&&&&printf(&\r\n&);
&&&&return&0;
程序输出的，图7：
上面是可以联通的情况，那找一个不可以联通的情况试验一下：
#include&&afxwin.h&&&&&&&&&&//&MFC&core&and&standard&components
#include&&afxext.h&&&&&&&&&&//&MFC&extensions
#include&&afxdisp.h&&&&&&&&&//&MFC&Automation&classes
#include&&afxdtctl.h&&&&&&&&&//&MFC&support&for&Internet&Explorer&4&Common&Controls
#include&&afxcmn.h&&&&&&&&&&&&&//&MFC&support&for&Windows&Common&Controls
#include&&stdio.h&
#include&&stdlib.h&
#include&&function.h&
int&main()
&&&&printf(&开始&测试\r\n\n\n&);
&&&&byte&ChessData[10][18];
&&&&int&i,j;
&&&&for&(j&=&0;&j&&=&10;&j++)
&&&&&&&&for&(i&=&0;&i&&=&18;&i++)
&&&&&&&&&&&&ChessData[j][i]&=&rand()%2;
&&&&&&&&&&&&printf(&%2d&&&,ChessData[j][i]);
&&&&&&&&printf(&\r\n&);
&&&&POINT&p1;&&//&这里改了
&&&&p1.x&=&7;
&&&&p1.y&=&7;
&&&&POINT&p2;&&//&这里改了
&&&&p2.x&=&10;
&&&&p2.y&=&6;
&&&&if&(DecideChessIfRemove(p1,&p2,&ChessData))
&&&&&&&&printf(&2点相连\n\n&);
&&&&&&&&printf(&2点不相连！~\n\n&);
&&&&for&(j&=&0;&j&&=&10;&j++)
&&&&&&&&for&(i&=&0;&i&&=&18;&i++)
&&&&&&&&&&&&printf(&%2d&&&,ChessData[j][i]);
&&&&&&&&printf(&\r\n&);
&&&&return&0;
程序输出，图8：
好了大功告成，说明我们的函数还是有些用的
最后感谢大家能看我一篇文章
最后请看图9：
谁能给我分析一下，为什么2个图标红线处不一样呢？
我没有深入的进行调试，对不起了大家，如果用我的代码写外挂，有什么bug，我有免责申明啊连连看大局消除算法 - 编程当前位置:& &&&连连看大局消除算法连连看大局消除算法&&网友分享于：&&浏览：79次连连看全局消除算法
好久没写技术博客了。Iteye依然这么亲切！
内存分析了连连看内部数据，找出了方块摆放的那一段数据，用程序把它读出来，放到一个二维数组里面，构成一个矩阵。
这些数据就做为这个算法的数据基础。
这是今天突发奇想，写出来的代码，结合内存读出来的数据，可以瞬间把连连看里面的方块消得个精光。
一阵电闪雷鸣，瞬间之后，就变成下面这样子了：
但本篇文章不讲这个外挂程序。只讲里面涉及到的连连看全局算法。
本算法事实上也就是在一般的连连看消除算法上，包装了下。写过连连看游戏的朋友应该都明白怎样判断两个方块是否可以消除，而本算法就是循环地判断全局所有的可消除的方块，一对一对地消掉，直到最后没有方块时才停止程序。
其实说来说去，这个算法的本质也就是深搜。基本思路如下：
从左上角第一格开始，用深搜查找它在两个转弯之内可以碰到的和它一样的方块，如果找到，就消去，把矩阵里面相应的两个数值也设成0。再以第二格为起点，用同样的方法查找和它一样的方块。以此类推，一格一格地，一行一行地遍历整个矩阵。第一遍过去，基本上都有剩下方块。于是进行第二次遍历。那么怎么判断全局的方块都已经消完了？很简单，一开始看一共有多少方块，每消去一对就减2，直到为0时就停止遍历。
思路看起来很简单，但其实限制条件特别多，写起来很可能会有哪一方面没考虑到。于是调了好久。。。
下面就直接给出算法的代码，结合上面的思路，应该很容易看懂：
#include &iostream&
#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};
bool FindTheSame(int &x, int &y, int d0, int turnCnt,bool turn)
//x表示行，y表示列
{ //d0表示前一步的方向,用来防止它往回走; turnCnt表示转弯的次数，超过两个就不算了，返回
//turn表示从上一步到这一步，是否已经转弯了
if(turn) turnCnt ++;
if(turnCnt & 2)
int d = 0;
for(; d & 4; d ++)
if(d == (d0+2)%4) //其它三个方向没搜索完之前，不让它按原方向返回
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) //越界了
if(newx == gx && newy == gy) //找到的是原来的那个
if(m_matrix[newx][newy])
if(d0 &= 0 && d != d0) if(turnCnt+1 & 2)
if(m_matrix[gx][gy] == m_matrix[newx][newy])
x += dir[d][0];
y += dir[d][1]; //返回x,y数值
bool flag =
if(d0 &= 0 && d != d0) flag =
if(FindTheSame(newx,newy,d,turnCnt,flag))
//跳到下一个空格
if(turn) turnCnt --;
int main()
int i,j,tmpi,
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])
tmpi = gx =
tmpj = gy =
if(FindTheSame(tmpi,tmpj,-4,0,false)) //-4是为了避免干扰在FindTheSame里面对是否原路返回的判断
//能到这里，说明已经找到一对了，消去
m_matrix[i][j] = 0;
m_matrix[tmpi][tmpj] = 0;
curCnt --;
注意，这个算法用于边缘同行或同列上不能消除的情况。如果要改为边缘可消除，那么给数组加一圈0就行了。
这些代码调了很久，调到最后头都有点晕了，基础不太好。。
有不足或有改进的地方，欢迎大家在评论中指出来，一起学习！
12345678910
12345678910
12345678910 上一篇：下一篇：文章评论相关解决方案 12345678910 Copyright & &&版权所有本帖子已过去太久远了，不再提供回复功能。