连连看算法[zszen式连连算法]070626更新

zszen

理论和实践的结合,完美的连连看算法

原理是扫描横排或是纵排是否存在全空行/列  只有存在这种状况 连线的拐点才能达到2个以内

070626最新修改
增加了例子,特效算上不到200行代码

1. //矩阵
   
2. /*
   
3. [0,2,1,0]
   
4. [0,1,2,0]
   
5. [0,1,1,0]
   
6. [0,0,1,0]
   
7. 
   
8. [0,2,1,0]
   
9. [0,1,0,0]
   
10. [0,1,1,0]
    
11. [0,0,0,2]
    
12. 
    
13. [0,2,0,1]
    
14. [0,1,0,0]
    
15. [1,1,1,2]
    
16. [0,1,1,0]
    
17. */
    
18. //前两个是两个目标点,最后一个是整体最大区域 目标点修改 矩阵也需要修改
    
19. //ary = [[0, 2, 1, 0], [0, 1, 2, 0], [0, 1, 1, 0], [0, 0, 1, 0]];
    
20. //trace(outPath({i:0, j:1}, {i:1, j:2}, {i:4, j:4}));
    
21. //ary = [[0, 2, 1, 0], [0, 1, 0, 0], [0, 1, 1, 0], [0, 0, 0, 2]];
    
22. //trace(outPath({i:0, j:1}, {i:3, j:3}, {i:4, j:4}));
    
23. ary = [[0, 2, 0, 1], [0, 1, 0, 0], [1, 1, 1, 2], [0, 1, 1, 0]];
    
24. trace(outPath({i:0, j:1}, {i:2, j:3}, {i:4, j:4}));
    
25. function outPath(now, then, limit) {
    
26. var mini = Math.min(now.i, then.i);
    
27. var maxi = Math.max(now.i, then.i);
    
28. var minj = Math.min(now.j, then.j);
    
29. var maxj = Math.max(now.j, then.j);
    
30. var limiti = limit.i;
    
31. var limitj = limit.j;
    
32. var haveLine;
    
33. var i = 0;
    
34. var j = 0;
    
35. ///纵列 当用纵列来扫描 行i就限制在两目标点之间
    
36. for (i=0; i<limiti; i++) {
    
37.   haveLine = true;
    
38.   for (j=minj; j<=maxj; j++) {
    
39.    //trace([i, j, ary[j]]);
    
40.    if (!(i == now.i && j == now.j) && !(i == then.i && j == then.j)) {
    
41.     if (ary[j] == 1) {
    
42.      haveLine = false;
    
43.      break;
    
44.     }
    
45.    }
    
46.   }
    
47.   if (haveLine) {
    
48.    var check = unitEmpty({i:i, j:now.j}, {i:now.i, j:now.j}) && unitEmpty({i:i, j:then.j}, {i:then.i, j:then.j});
    
49.    if (check) {
    
50.     break;
    
51.    } else {
    
52.     haveLine = false;
    
53.    }
    
54.   } else {
    
55.    haveLine = false;
    
56.   }
    
57. }
    
58. if (haveLine) {
    
59.   return haveLine;
    
60. } else {
    
61.   //行列 当用行列来扫描 列j限制在两个目标点之间
    
62.   for (j=0; j<=limitj; j++) {
    
63.    haveLine = true;
    
64.    for (i=mini; i<=maxi; i++) {
    
65.     if (!(i == now.i && j == now.j) && !(i == then.i && j == then.j)) {
    
66.      //trace([i, j, ary[j]]);
    
67.      if (ary[j] == 1) {
    
68.       haveLine = false;
    
69.       break;
    
70.      }
    
71.     }
    
72.    }
    
73.    if (haveLine) {
    
74.     var check = unitEmpty({i:now.i, j:j}, {i:now.i, j:now.j}) && unitEmpty({i:then.i, j:j}, {i:then.i, j:then.j});
    
75.     if (check) {
    
76.      break;
    
77.     } else {
    
78.      haveLine = false;
    
79.     }
    
80.    } else {
    
81.     haveLine = false;
    
82.    }
    
83.   }
    
84.   return haveLine;
    
85. }
    
86. }
    
87. function unitEmpty(now, then) {
    
88. //取得两目标点是否其间可穿越,必须是同行或是同列
    
89. var mini = Math.min(now.i, then.i);
    
90. var maxi = Math.max(now.i, then.i);
    
91. var minj = Math.min(now.j, then.j);
    
92. var maxj = Math.max(now.j, then.j);
    
93. //trace([mini, maxi, minj, maxj]);
    
94. var haveLine = true;
    
95. if (mini == maxi) {
    
96.   for (var j = minj+1; j<maxj; j++) {
    
97.    if (ary[mini][j] == 1) {
    
98.     haveLine = false;
    
99.     break;
    
100.    }
     
101.   }
     
102.   return haveLine;
     
103. } else if (minj == maxj) {
     
104.   for (var i = mini+1; i<maxi; i++) {
     
105.    if (ary[minj] == 1) {
     
106.     haveLine = false;
     
107.     break;
     
108.    }
     
109.   }
     
110.   return haveLine;
     
111. }
     
112. return false;
     
113. }

复制代码

[ 本帖最后由 zszen 于 2007-9-2 17:39 编辑 ]

ycccc8202

没看出什么时候是false..

zszen

沉了 沉了 这么好的算法 没人顶真可惜

quhuan

又没原文件,又没图释,又没注释,啥都没有,懒的看

柳世杀神

啊～！好算法！收藏！顺便顶！

柳世杀神

不过建议还是加上注释

ycccc8202

假如这样的情况
ary = [[1, 1, 1, 1], [1, 2, 0, 1], [1, 1, 2, 1], [1, 1, 1, 1]];

结果返回的是false....

是不是limit也要跟着设置?

zszen

循环那个位置 有问题 呆细琢磨 之前我设置的外循环是 在min和max之间 包括他们 后来又给改成了limit的最大和最小了  具体问题还需要多画图

quhuan

刚学flash的时候写过一个连连看.考虑的情况有多种
你现在有几种情况,返回是false的

jevin

:L 连个注释都没啊 这怎么看 以前的算法好像是 看折点

zszen

感觉就用一个fn没必要注释吧 代码也不长 ,除非你不想看懂就想改代码直接用

zszen

更新了 更新了 还增加了 注释和图解

ycccc8202

..怎么能通过两个位置来确定一个矩形范围呢?>>>

//矩阵
/*
[0,2,1,0]
[0,1,0,0]
[0,1,1,0]
[0,0,0,2]
*/
ary = [[0, 2, 1, 0], [0, 1, 0, 0], [0, 1, 1, 0], [0, 0, 0, 2]];

trace(outPath({i:0, j:1}, {i:3, j:3}, {i:4, j:4}));

//打印结果看看

quhuan

有这么几种情况
1. 两点之间没有拐点
2. 两点之间只有一个拐点
3. 两点之间有两个拐点

第一中情况,很好判断.不说了,
第二种情况:分别取两点横\纵方向,通路的线段,如果有交叉点,则通过
第三种 :a,b两点
取a点,先取其横向通路线段的点加入列表A,从A列表第一个点开始,取其纵向通路的点线段,如果该线段与b点的横向线段交叉则相通.........(其他情况类似)

太拗口了,表达不清楚

第三中情况的图

[ 本帖最后由 quhuan 于 2007-6-22 15:03 编辑 ]

zszen

这回没有问题了 ><

quhuan

恩
ary = [[0, 2, 0,1], [0, 1, 0, 0], [1, 1, 1, 2], [0, 1, 1, 0]];
trace(outPath({i:0, j:1}, {i:2, j:3}, {i:4, j:4}));
这样返回true

[ 本帖最后由 quhuan 于 2007-6-22 15:28 编辑 ]

zszen

唉 哈 不好意思 第一个循环里面的襄套循环 j<=maxj 不是j<maxj 疏忽 疏忽 呵呵

柳世杀神

终于有注释了～
呵呵，谢谢楼主的热心啊～

zszen

严重谢谢ycccc8202和quhuan帮我测试

jevin

:) 谢谢版主 HOHO 不错 ~

zzjinzaghi

有点象迷宫哈！·

tonson

各位朋友,谁下载好了[超级收集2500多个FLASH源代码下载演示]?现在不能下载,哪个朋友能传给我,QQ343776259,谢谢

HBrO

当年我写过,也一样沉得很快

ghdqlz

应该顶呀

紫翎炽天使

看的有点蒙 继续看:loveliness:

mma

这坟挖得好 顶下慢慢看.