Post By：2008/6/25 11:08:25
图－：
0, 0, 0, 0, 0, 0, 0, 0 , 0, 0
0, 8, 0, 0, 0, 0, 0, 0 , 0, 0
0, 0, 0, 0, 0, 0, 0, 0 , 0, 0
0, 0, 0, 0, 0, 0, 0, 0 , 0, 0
0, 0, 0, 0, 0, 0, 0, 0 , 0, 0
0, 0, 0, 0, 0, 0, 0, 0 , 0, 0
0, 0, 0, 0, 0, 0, 0, 0 , 0, 0
0, 0, 0, 0, 0, 0, 0, 0 , 9, 0
0, 0, 0, 0, 0, 0, 0, 0 , 0, 0
这是一张连连看的地图，假设标8和9的部分是两张相同的牌。
在数组矩阵中，0表示没有牌，大于1表示有牌。至于是什么牌，那是随机的了。
不要告诉我，你说的“布局算法”是指怎么把牌刚刚好放上去，那个无所谓什么
算法，你只要首先在地图数组中准备好偶数个1，在布牌时保证每种牌是偶数个
（不同种类的牌用大于1的数来表示），相应地放入每个1的位置上就可以了。
一、计算地图上这两张牌能不能连通(当然能了，哈哈）。
这是连连看寻路算法的第一步。
先定义一下两张牌能连的充分条件：
1.两张牌是同一种。
2.两张牌之间有一条全是0的路可以连通。
3.这一条路不能有两个以上的拐角(corner)
满足这三个条件，就可以认为这两张牌是可以连的。
首先，我们依据前两个条件来完成一个基本的寻路算法。
我们的目的是从8到9找出一条可以连通的路来。
那么很明显从8到9的第一步一其有四个方向可以选择，分别是东，南，西，北
（e, s, w, n以中国地图方向为标准）四个方向，在第一步中我们首先假设四
个方面没有任何优劣，那么我可以任意选择一个方向移动，那就是东面吧。
图二：
0, 0, 0, 0, 0, 0, 0, 0 , 0, 0
0, 8, －8, 0, 0, 0, 0, 0 , 0, 0
0, 0, 0, 0, 0, 0, 0, 0 , 0, 0
0, 0, 0, 0, 0, 0, 0, 0 , 0, 0
0, 0, 0, 0, 0, 0, 0, 0 , 0, 0
0, 0, 0, 0, 0, 0, 0, 0 , 0, 0
0, 0, 0, 0, 0, 0, 0, 0 , 0, 0
0, 0, 0, 0, 0, 0, 0, 0 , 9, 0
0, 0, 0, 0, 0, 0, 0, 0 , 0, 0
我从8向东移动了一步，所以到达了-8的位置，我之所以可以移到-8位置，很明显，
是因为-8的位置上原来是一个0，表示没有牌阻挡。
那么现在寻路的问题就变成了，如何从－8找连通9的路了！
说到这里应该明白了吧，好多费话，有点像娘们在说话。
所以目前的寻路算法归结为一个递归算法的基本问题。
先从8到找到下一个结点－8，再用同样的规则，从－8找到下一个结点，比如－88。。。
图三：
0, 0, 0, 0, 0, 0, 0, 0 , 0, 0
0, 8, －8, －88, 0, 0, 0, 0 , 0, 0
0, 0, 0, 0, 0, 0, 0, 0 , 0, 0
0, 0, 0, 0, 0, 0, 0, 0 , 0, 0
0, 0, 0, 0, 0, 0, 0, 0 , 0, 0
0, 0, 0, 0, 0, 0, 0, 0 , 0, 0
0, 0, 0, 0, 0, 0, 0, 0 , 0, 0
0, 0, 0, 0, 0, 0, 0, 0 , 9, 0
0, 0, 0, 0, 0, 0, 0, 0 , 0, 0
如果一直都能OK，没有阻碍的话，最后找到了9，就算成功以，如要有一步不能走下去了，
就再退回上个结点，向别的方向发展，都不行，就再退回上级结点，再向别的方向发展，
这里的逻辑就是递归的思想了。
用这样的方法写出来的算法已经能在最优的情形下用了，比如从8，到－88，哈哈。
但在稍微复杂的情况下，会产生奇多的递归结点。P4机也跑不动啊。我试过，哈哈。
那么第二步就是为（e,s,w,n）四个方向加权，也就是让它们之间有一个优先权，说白了就
是先试哪一条路。决定的法则应该有好几个吧，比如以9号的位置来看，它处于8号的东南面，
那试路时当然应当优先选择东面和南面，再比如9号如果牌8号的正东面，那当然是选择正东了。
再比如，当走到－8的位置时，明显只能再走三个方向，因为它是不能回头的。
经过这样的处理，递归算法生成的结点数会明显变少，会更快的找到成功的路。但性能在最坏情况
下没有本质改变。
接下来，第三步，我们把第三个充分条件加进来，来解决根本问题。
3.这一条路不能有两个以上的拐角(corner)
按照面向对象的思想，很自然的，我给每个在递归算法中生成的位置结点加上了个corner的属性，
来记录这条路到目前为止拐了几个角。
这样一下子就好办了啊。如果发现这个结点已经拐了两个弯时，如果要再拐弯，或者到达9之前注定
要再增加cornor时，就果断over，返回上级结点。
好，就说到这儿吧，不能再多说了，否则就是等于把代码公开了，哈哈。
注意，要把二、三两步的条件综合起来详细规划一个个可能性，尽可能提早让不可能的结点OVER，
这就是提高性能的关键吧。你的算法预见性越强，性能就越高吧。
我们的算法在赛扬500，256M的机器上，10万次平均结果是一次运算花时不超过0.1毫秒,算得还不
精确，速度确实很快，因为在很坏的情形下，产生的最大结点数是690几个，这样必然会很快的
，详细的数据已经记不清了。
说了这么多了，应当明白第一步连通算法的思路了吧，我所知道的，都已经尽可能的讲出来了。
这个算法完全是自己按照连连看的特点，度身定做的。因为是一步步test出来的，所以我个人
觉得是很自然的，没有任何高深的地方，完成后，性能也很好，这才觉得是如此的简单。相信大家
仔细看看就能写出自己的算法来的吧。
二、整个地图有没有解？？？可以连通的总牌数？
这是一个问题。
解决这个问题之前，我们先来解决提示功能(hint）就是为玩家提供提示，哪一对牌可以连
通。
我的做法是，先把整个地图中相同牌归到一起，用数组也好，链表也好。
像这样，
4,4,4,4
5,5,5,5
6,6,6,6
......
然后计算比如4个4之间有哪两对可以连，至于如何判断能不能连，第一步算法已经实现了吧，哈哈。
一发现有可以连的牌就退出来，告诉玩家这两张牌可以连啊！
这就OK了。
这完全是建立在第一步算法的基础上实现的。
好的，hint功能可以了，
那么，整个地图没有解的算法是不是出来了？
是的，如果找不到可以hint的牌，那当然就是没有解了！
把所有可以hint的对数记下来，就是总的可以连通数了。
至此，与连连看所有算法有关的问题解决完毕。
第二步算法的实现，明显开销要大很多，最坏情况应当会是单次连通算法计算量的大约50倍以上
（与牌的总数量和摆的位置有关）还好在一般的服务器上单次连通计算花的时间实在太少了，
实际运行中完全可以很流畅。以上数据都是我估计的理论值，因为实际测试时一直没有问题，
我也懒得计算出真正比较可靠的均值了。
这一部分也是我认为可以有所改进的部分，公开出来，也希望大家能提供一些更好，更巧妙
的方法，我觉得我计算连通数和有无解的方法是比较笨的方法，几乎是仗着基本的算法快，一
个一个算出来的。有没有更好的方法呢？期待中，我也会再想想，太忙，太懒，主要是懒，觉得
可以用就行了。
很久没有写这么长的东西了，除了程序，哈哈。
最后，真心希望能给大家一点帮助。也希望， jzgenius网友能从中找到自己的答案。
更希望大家能提出批评改进的实际建议，让我也提高一下。
