连连看消除算法

1、连连看消除算法说明：本算法为个人意愿，意在实现功能，并非最优，便于大家理解连连看游戏的实质。 游戏规则：连连看游戏的消除规则玩过了应该挺容易理解，就是两点之间只能用水平或者竖直线段连接，最多不能超过2个拐点。所以分成了4种情况，1、 直接相连 3、 Z型相连2、 转一次弯相连 4、 U型相连下面开始提出一种直观的算法：我们来判断两个物体能否消除。1、 我们从一个物体出发，沿十字向外搜集直接相连点，遇到其他物体就终止当前方向搜索。对两个待判断的物体都进行十字点收集。2、 我们定义一下直接相连：两个点处于水平或者竖直位置，并且中间没有任何其他物体阻挡。A、如果是处于消除情况1（直接相连）的情况，那

2、么第二个点应该在第一个的十字搜集点上（直接连）B、如果是处于消除情况2（转一次弯）的情况，那么物体1十字线上的某点肯定能够和2直接相连C、如果是处于消除情况3或者4，那么物体1十字线上的某点肯定能够和物体2十字线上的某点直接相连D、边界问题我们单独考虑，有的游戏规则中可以边界外走线，有的则不可以，这个对我们算法没有影响。所以整个程序实现就简单了，伪代码：函数A，判断两点是否可以直接消除函数B，收集指定点十字方向全部直接相连点如果两点可直连则可消除遍历2的直连点如果点1和点2十字中某点可直连则可消除 遍历1，2的直连点如果有可直连点则可消除给出一个没完成的python代码供参考：'

3、9;'Description:link link game auto solver algorithm.Author:winxosDate:2011-05-18'''import randomsize=10m=0 for x in range(size) for y in range(size)defcreatemap():defcreatepos():return random.randint(0, size-1), random.randint(0, size-1)deffillpair(n):a=createpos()while ma0a1!=0:a=cr

4、eatepos()b=createpos()while mb0b1!=0 or b=a:b=createpos()ma0a1=nmb0b1=nfor i in range(20):fillpair(random.randint(1, 9)passdefisdirectlink(a, b):#a,b is point#return 1 means can link directlyif a0=b0 and a1=b1: #same point return false return 0if a0=b0: #Verticalif a0=0 or a0=size-1: #bound is linka

5、blereturn 1sa=a1sb=b1ifsb<sa: #field from sa to sb, sa<sbsa=b1sb=a1for i in range(sa+1, sb-1):if ma0i!=0:return 0return 1if a1=b1: #Horizonif a1=0 or a1=size-1: #bound is linkablereturn 1sa=a0sb=b0ifsb<sa: #field from sa to sb, sa<sbsa=b0sb=a0for i in range(sa+1, sb-1):if mia1!=0:return

6、0return 1passreturn 0defonelinepoint(a): #return the cross directly linkable points. r=i=a0-1while mia1=0 and i>0:r.append(i, a1)i-=1i=a0+1while mia1=0 and i<size:r.append(i, a1)i+=1j=a1-1while ma0j=0 and j>0:r.append(a0, j)j-=1j=a1+1while ma0j=0 and j<size:r.append(a0, j)j+=1return rdefislinkable(a, b): #core function ifisdirectlink(a, b):return 1sa=onelinepoint(a)sb=onelinepoint(b)for x in sa:ifisdirectlink(x, b):return 2for x in sb:ifisdirectlink(a, x):return 2for x in sa:for y in sb:ifisdirectlink(x, y):return 3return 0defprt(n):print(&qu