还是连连看算法的问题(整图是否有解)
现在判断两点是否连通已经完成,
接下来就是要解决整图是否有解,以及加入重新洗牌的功能
对于整图是否有解,其实按最垃圾的方法,就是对每一个牌进行循环,然后判断与另外的是否能连通
但这样实在太......
1.希望各位能推荐个好方法,来判断整图是否有解, (这个问题最重要)
2.如果我在一个连接消除后,然后进行整图是否有解的判断.这样是不是会太慢,是不是应该搞个线程在那边算是否有解?
3.最后就是提醒道具,怎么实现来给玩家提醒哪两个可以连?
问题点数：50、回复次数：11Top
1 楼zbo（黑魔导士比比）回复于 2005-04-04 21:26:34 得分 0
不懂算法。不过按照连连看的玩法。在牌堆内部的牌只需要判断周围四个是否跟他连接。是不是？Top
2 楼ckc（火）回复于 2005-04-05 08:54:40 得分 0
我玩过的连连看好象不一定整图有解的
有的就是没解
你只要有一些可以洗牌的功能应该就可以了
或者是不是可以用随机一对一对加上牌的办法解决？
因为是一对一对加上去的，所以肯定有解（按相反顺序取下即可）Top
3 楼ZhangYv（迎着朝阳,走向地狱）回复于 2005-04-05 09:36:05 得分 0
如何消除的规则需要自己定，普遍做法是如果两节点间需要拐弯两次就判断不合法。
0. 玩家选定一个连接后，判断该连接是否合法。如果合法消除，转过程1
1. 后台计算出一条可行的解，如果无解那么随机洗牌并且重复过程1，直到洗出有解的图
2. 玩家使用提醒道具，把后退计算出的解提示给玩家。
Top
4 楼lovewindy（LOVE风云）回复于 2005-04-06 08:15:58 得分 0
to:ckc(火)
不好意思,我好像理解不了你的意思,不知道能否详细讲解一下
to:ZhangYv(Show you my money)
羡慕啊，三颗星星，呵呵．对于该游戏的流程我已经清楚了，而且也解决了判断两点是否连通的算法，我现在要解决的是，如何去判断整图有解，希望能给出个解决方法，
谢谢Top
5 楼ZhangYv（迎着朝阳,走向地狱）回复于 2005-04-06 09:17:03 得分 0
就是我说的 1. 后台计算出一条可行的解，如果无解那么随机洗牌并且重复过程1，直到洗出有解的图
后台计算是一个穷举剪枝的过程，从第一个节点开始依次判定。一旦找到一条可行的连接就立刻返回，所以效率不会如想象中的那么糟。Top
6 楼lovewindy（LOVE风云）回复于 2005-04-06 15:08:37 得分 0
to: ZhangYv(Show you my money)
您所说的后台..是不是再开一个线程,让它在那边算?
如果能很早地找到可连接点,那这个算法倒还行,但如果遇到最坏条件,那.....Top
7 楼shenqhy（love）回复于 2005-04-08 08:16:44 得分 25
按图形的数量,建个二维数组,把同样的一些图形放在一组中,然后只要搜每组内是否可以连通.Top
8 楼ZhangYv（迎着朝阳,走向地狱）回复于 2005-04-08 09:33:42 得分 0
最坏条件也就O(N^2)，因为对被完全包围的图形就可以完全排除不进行比较，所以效率仍然可以接受。Top
9 楼lovewindy（LOVE风云）回复于 2005-04-09 08:13:27 得分 0
呵,谢谢ZhangYv(Show you my money)
不过感觉好像还是shenqhy(love)的算法好一点,以一点空间换取时间上的进步,Top
10 楼ZhangYv（迎着朝阳,走向地狱）回复于 2005-04-09 10:39:09 得分 25
嗯，对。但是在重新洗牌或位置变化的时候会稍微麻烦点，二维数组中的值要同步改变。Top
11 楼wlj1800（跑步进入原始社会）回复于 2005-04-09 11:31:44 得分 0
http://bbb123.com/down.asp?UserID=116189
教学视频下载值得一看Top
