- 浏览: 190924 次
- 性别:
- 来自: 长沙
文章分类
最新评论
-
在世界的中心呼喚愛:
思路很好
连连看全局消除算法 -
tianaozhu:
请问,我修改了词库和源文件怎么就不好用了, 我源文件是: My ...
自己动手开发翻译软件(Java版) -
Arlrn:
博主你好,最近在学习排序算法,看了你的博客,你的直接插入排序, ...
各种排序算法的实现及其比较 -
sharong:
有一个明显错误,很显然冒泡排序的时间复杂度是O(n^2)
各种排序算法的实现及其比较 -
julydave:
希尔排序不太对吧。。
各种排序算法的实现及其比较
好久没写技术博客了。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就行了。
这些代码调了很久,调到最后头都有点晕了,基础不太好。。
有不足或有改进的地方,欢迎大家在评论中指出来,一起学习!
发表评论
-
一个简单的字符组合算法
2011-07-27 13:18 1185有个朋友问了我这个问 ... -
object-c笔记一
2011-07-22 11:03 846(本笔记只是简单的记录,只给自己看) 接口的定义: ... -
VC2010中C++的右值引用新特性
2011-05-27 13:37 1464// RightValue.cpp : Defines ... -
各种排序算法的实现及其比较
2011-05-13 22:42 13761排序算法是笔试和面试中最喜欢考到的内容,今晚花了好几个小时的时 ... -
STL在ACM中的应用
2011-04-09 01:41 2301STL 提供三种类型的组件:容器、迭代器和算法,它们都支持泛型 ... -
linux下用命令编译/调试C++程序
2011-04-01 14:17 2991先安装gcc : sudo apt-get insta ... -
完全背包问题
2011-03-29 23:01 1649看这篇日志之前,请先阅读我的上一篇日志,关于0/1背包 ... -
0/1背包问题的动态规划详解
2011-03-29 22:57 1484动态规划是用空间换时间的一种方法的抽象。其关键是发现子问题 ... -
最长上升子序列问题的几种解法
2011-03-29 22:55 2498拿POJ 2533来说。 Sample Input 7 ... -
用BFS找最短路,并打印路径
2010-12-23 02:19 6086我想大部分读者都用Floyd或者Dijstra算法,甚至dfs ... -
插入排序的另一种写法
2010-12-14 01:39 1150一般的插入排序方法想必大家都写过,基础好的几分钟就可以写出来了 ... -
北大ACM题库习题分类与简介
2010-12-06 13:57 1722acm.pku.edu.cn转自:http://www.stu ... -
对Windows程序中设备上下文DC(device context)的理解(转)
2010-11-08 00:58 1589对Windows程序中设备上 ... -
POJ1753-位操作
2010-11-03 01:30 1086Flip Game Time Limit ... -
MFC学习笔记(九)
2010-10-30 01:47 1340前面已经讲了够多的基础性的东西了,还有一些,但我想还是之后遇到 ... -
MFC学习笔记(八)
2010-10-30 00:55 1005MFC把早期的窗口类的功能分成三个部分:数据存储、管理部分,数 ... -
MFC学习笔记(七)
2010-10-28 01:29 936创建一个普通的Win32 Application,加上一个.c ... -
MFC学习笔记(六)
2010-10-28 01:16 1071先来了解几个类 1、CObject类 有相当一部分类的基 ... -
MFC学习笔记(五)
2010-10-27 01:55 1415早期的MFC应用程序框架结构由两个对象组成:应用程序类CWin ... -
MFC学习笔记(四)
2010-10-27 00:28 1130前面写了那么多代码,但很多东西都是固定的,我们需要写的主要是消 ...
相关推荐
希望帮到有需要的你 新年快乐
连连看算法的JAVA实现,使用递归,可达到无限拐点
连连看核心算法.rar 连连看核心算法.rar 连连看核心算法.rar 连连看核心算法.rar 连连看核心算法.rar 连连看核心算法.rar
小游戏连连看的详细算法介绍,供大家参考学习,是doc格式。
C++实现的连连看算法,一个例子可以明白C++语法和开发 的基础
改变A*寻路算法中的估价函数打造连连看的寻路算法 源码
连连看算法 一 连连看的要求 二 任意两点能否连通 三 地图无解提示 四 连接提示功能 五 道具问题 六 地图问题
NULL 博文链接:https://hexlee.iteye.com/blog/455257
主要介绍了C++连连看判定图形消除算法
java版连连看算法java版连连看算法java版连连看算法
连连看的核心算法,基于集合形式搜索路径。
android 连连看算法android 连连看算法android 连连看算法
主要为大家详细介绍了C++实现连连看消除算法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
功能较为齐全,算法简单,只需判断第一次和第二次按键左右位置
连连看游戏里边涵盖了:随机分布算法;遍历查找算法;时间进度控制; 这些算法全部是设计并完成的,感觉比别人的算法要简单易懂!
连连看的具体算法.doc
连连看核心算法
易语言源码连连看核心算法.rar 易语言源码连连看核心算法.rar 易语言源码连连看核心算法.rar 易语言源码连连看核心算法.rar 易语言源码连连看核心算法.rar 易语言源码连连看核心算法.rar
程序的关键在于判断用户连续点击的两个图案能否消除。两个图片可以消除的条件有两个: 图片相同 图片间连线的转角数不得超过2 。
连连看 java算法 基于安卓手机开发的游戏程序