主题：（连连看路径的判定）如何用最快的方法判定可通路径？
Mato完整版
[专家分：1270] 发布于 2008-04-24 21:32:00
连连看大家都玩过，就是一个N×M板上，每个格子都有一个属性，每次可以消去两个格子。
这两个格子必须符合以下3条：
（1）两个格子的属性必须相同。
（2）两个格子之间有路径。
（3）路径的转折点不能多于K个。
其中（2）、（3）的判定比较难，我有一种方法，假设目前的板是这样的：
X 1 2 2 1 3 3
3 2 3 2 3 4 4
X 3 1 2 1 1 3
4 3 2 1 2 4 2
数字表示属性,X表示已消去的格子。
把周围加上一圈X：
X X X X X X X X X
X X 1 2 2 1 3 3 X
X 3 2 3 2 3 4 4 X
X X 3 1 2 1 1 3 X
X 4 3 2 1 2 4 2 X
X X X X X X X X X
然后用<路径搜索-迷宫2-转弯次数>的方法就可以判定。
然而，这种方法太慢了。
我觉得还有更快的方法，大家能帮帮我吗？
回复列表 （共6个回复）
沙发
moz [专家分：37620] 发布于 2008-04-25 00:43:00
|
| |
-----A---------+-------+ C
| | |
| | |
| | |
-----+---------B-------+ D
| |
|
1. 在同一条直线上
2. 某条直线有交叉点
3. 平行线有通道
板凳
Mato完整版 [专家分：1270] 发布于 2008-04-25 12:20:00
怎么判断平行线有通道呢？
3 楼
moz [专家分：37620] 发布于 2008-04-25 17:13:00
C,D 点在同一Y轴上
判断是否存在通道。
可以这样子做
1. 获得A所在的同X轴或同Y轴的所有点（集合AA/十字线）
2. 获得B所有的同X轴或同Y轴的所有点（集合BB/十字线）
3. 有方向地从近到远遍历集合AA，寻找集合BB中是否存在同X轴/或同Y轴的点
4. 两点间是否全空 - 获得路径。
4 楼
Mato完整版 [专家分：1270] 发布于 2008-04-25 20:44:00
我不懂，能不能说清楚点？？
5 楼
moz [专家分：37620] 发布于 2008-04-26 05:16:00
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 [color=0000ff]33[/color] 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 [color=0000ff]79[/color] 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100
函数是否能连(A点, B点)
A点的坐标是 3, 3 (以竖十横个为基准,只是一个概念问题,暂别论公认的XY轴)
跟A点同轴的有:
竖线: 13 23 33 43 53 63 73 83 93
横线: 31 32 33 34 35 36 37 38 39
以这个十字线为集合E(A)
跟B点同轴的有:
竖线: 19 29 39 49 59 69 79 89 99
横线: 71 72 73 74 75 76 77 78 79
以这个十字线为集合E(B)
遍历(应该优化从点往外延伸,从而找到最短路径才对,这里暂不讨论)
从E(A)开始 13
到E(B)里找有没有同行或同列的点:可以找到: 19,73
检查13-19,13-73之间是否空位,能否相通,调用函数通道检查(点1,点2)
如果不符条件,检查集合E(A)的下一个点.............全部点都检查完了没通道就是没有路径.
在一个平面里,如果要做像连连看这样的游戏,
很有必要预先检查并保存路径,一点即能知道结果,否则点了再去检查,就晚了点.
6 楼
moz [专家分：37620] 发布于 2008-04-26 05:18:00
还要补充一点,十字线不能跨越实点.
我来回复
您所在位置：