C大调如歌的行板
我也来发明山楂车轮
C++博客
首页
新随笔
联系
聚合
管理
随笔 - 32 文章 - 94 trackbacks - 0
<
2009年7月
>
日
一
二
三
四
五
六
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
6
7
8
常用链接
我的随笔
我的评论
我参与的随笔
留言簿
(8)
给我留言
查看公开留言
查看私人留言
随笔分类
C++(4)
钢琴(8)
其他(9)
算法(6)
图形学(13)
游戏编程(9)
随笔档案
2014年2月 (1)
2013年11月 (1)
2013年5月 (1)
2013年1月 (1)
2012年12月 (1)
2012年11月 (1)
2012年8月 (1)
2012年2月 (2)
2011年10月 (1)
2011年5月 (1)
2011年4月 (2)
2011年3月 (1)
2010年12月 (1)
2010年6月 (1)
2010年2月 (1)
2010年1月 (4)
2009年10月 (3)
2009年9月 (1)
2009年8月 (2)
2009年7月 (2)
2009年6月 (3)
好友连接
大学同班大牛人CK
大学同宿大牛人vczh
搜索
最新评论
1. re: 之前做的LOD动态地形
@kk
没错啊,直接在vs里面依据高度图重新计算顶点高度
--陈昱(CY)
2. re: 之前做的LOD动态地形[未登录]
大神,何咏说的“一般都是分块之后直接在GPU上面搞Displacement ”,什么是Displacement啊。Displacemen mapping 么?
--kk
3. re: 肖邦练习曲《离别》
多去钢琴有关的论坛交流~@溪流
--陈昱(CY)
4. re: 肖邦练习曲《离别》
@陈昱(CY)
仰慕~~
拜厄前50条水平,有空请多多指教!
--溪流
5. re: 肖邦练习曲《离别》
钢琴年龄比编程还长好多的说~~@溪流
--陈昱(CY)
阅读排行榜
1. shader toy 上练习,画了个baby grand piano(4806)
2. 乔治·温斯顿的C大调《卡农》(3376)
3. (原创)宇宙10个维度的一句话理解(3336)
4. 肖邦练习曲《牧羊人的笛子》(3310)
5. 李斯特《爱之梦》(3244)
评论排行榜
1. 之前做的LOD动态地形(10)
2. 多点触摸的GUI?(10)
3. 一个想法,实现n维超级立方体!!!初步成功!!!(第二章)(9)
4. 一个想法,实习n维立方体!!! (结束)(9)
5. 一个想法,用程序画出高维超立方体在三维上的投影!!!(1)(8)
以前写的一个N连看
这一周,我写好了一个连连看,在设计连连看的算法的过程中,我设计了一个可以控制连数的连连看算法,并把连连看改成了“
n
连看”,然后经过算法优化,使我的连连看算法在
20
连、无解、矩阵是
13*11
、最坏情况(一个周围空旷,一个被包围)下,运算速度仅
2
秒左右。而经过优化之前,到了
6
连的最坏情况下就已经慢得无法接受了。
基本的算法是这样的:
先写一个函数
f1
,判断点
1
和点
2
能否经过某个方向直线到达,方向有上、下、左、右四种
再写一个函数
f2
用于循环递归调用
f1
,思路是:如果起始点通过直线到达不了目标点,就把起始点可以直线到达的每个点当成下一次调用的起始点,直到找到目标点就立即返回。
f2
的参数包括:
n
连:用来控制递归深度;
2
个点(起始点和目标点),用来判断能够经过
n
连连接的
2
个点;
判断当前是“上下”或“左右”方向:由于某个点寻找目标点时,我引进了行走方向,这样可以节省一半的计算量。例如:如果当前方向是“上下”,直线找不到时,下一步递归对直线上的每个点的寻找,就只需要“左右”方向,不需要上下;
路径记录的列表。
以上是基本思路。
我的算法优化方法很简单,就是在原来基础上加上一个对应于所有点的数组,用来记录对应的点在第多少连的情况下仍然没有找到目标点。例如:假设总共只能
n
连,当前点已经被记录到经过
x
连仍然找不到目标点,这时,如果继续递归到第
n-x+1
连又来到该点,这时只剩下
x-1
连可以递归,而当前点已经记录过
x
连都无法到达,所以接下来的递归可以忽略。
这样,大大减少了无效的计算,原来在第
6
连最坏情况下算了
40
多秒得到无解,现在可以在
20
连最坏情况下计算
2
秒得到无解。
那个n连看的算法当时用一天写出来,非常兴奋。无奈电脑是内网,要保密,不能把代码直接传出来,之前想过有时间要贴出来,一直忘记了。现在在转到这个新开的blog。
只贴算法有关部分。用的是python语言:
1
class
CY_LianlianKan(
..):
2
def
__init__
(self):
3
self.m_Array
=
[]
#
存储内容的矩阵
4
self.m_LinkCount
=
0
#
需要连的总数
5
self.m_FirstPosition
=-
1
#
记下连的第一点
6
self.MaxWidth
=
13
#
矩阵宽
7
self.MaxHeight
=
12
#
矩阵高
8
#
其它初始化内容
9
#
----------------------------------
10
def
IsTargetXYValid(self,X,Y):
11
#
目标坐标是否有效,超过矩阵宽高即无效
12
#
----------------------------------
13
def
IsTargetXYBlank(self,X,Y):
14
#
目标是否空白可以通过
15
#
----------------------------------
16
def
GetArrayXY(self,X,Y):
17
#
获取矩阵坐标为XY的内容
18
#
----------------------------------
19
def
IsLineable(self,x1,y1,x2,y2,direction):
#
判断两点是否可以通过某方向直线连接
20
#
方向direction:1←2→3↑4↓
21
if
direction
==
1
:
22
if
y1
==
y2
and
x1
>
x2:
23
for
i
in
xrange(x2,x1
+
1
):
24
if
self.GetArrayXY(i,y1)
>
0:
25
return
False
26
return
True
27
elif
direction
==
2
:
28
if
y1
==
y2
and
x1
<
x2:
29
for
i
in
xrange(x1,x2
+
1
):
30
if
self.GetArrayXY(i,y1)
>
0:
31
return
False
32
return
True
33
elif
direction
==
3
:
34
if
x1
==
x2
and
y1
<
y2:
35
for
i
in
xrange(y1,y2
+
1
):
36
if
self.GetArrayXY(x1,i)
>
0:
37
return
False
38
return
True
39
elif
direction
==
4
:
40
if
x1
==
x2
and
y2
<
y1:
41
for
i
in
xrange(y2,y1
+
1
):
42
if
self.GetArrayXY(x1,i)
>
0:
43
return
False
44
return
True
45
return
False
46
#
---------------------------------------
47
def
IsNTurnReachable(self,x1,y1,x2,y2,path,n,LRorUD,hasReachPoint):
48
#
path成功时用于记录路径 n当前剩下的连数 LRorUD当前方向是上下还是左右
49
#
hasReachPoint 一个矩阵,用于记录矩阵中各个点目前已经经过多少连了还找不到目标点
50
if
n
<=
0:
51
return
False
52
if
LRorUD:
#
左右方向
53
for
x
in
xrange(x1
-
1
,
-
1
,
-
1
):
#
向左
54
if
self.GetArrayXY(x,y1)
==
0
and
hasReachPoint[y1
*
self.MaxWidth
+
x]
<
n:
55
if
self.IsLineable(x,y1,x2,y2,
3
)
or
self.IsLinable(x,y1,x2,y2,
4
):
56
path
+=
[x,y1,x2,y2]
57
return
path
58
else
:
#
到达不了,上下转弯,递归
59
hasReachPoint[y1
*
self.MaxWidth
+
x]
+=
1
60
p
=
self.IsNTurnReachable(x,y1,x2,y2,path
+
[x,y1],n
-
1
,False,hasReachPoint)
61
if
p
!=
False:
62
return
p
63
else
:
64
break
65
for
x
in
xrange(x1
+
1
,self.MaxWidth):
#
向右
66
if
self.GetArrayXY(x,y1)
==
0
and
hasReachPoint[y1
*
self.MaxWidth
+
x]
<
n:
67
if
self.IsLineable(x,y1,x2,y2,
3
)
or
self.IsLineable(x,y1,x2,y2,
4
):
68
path
+=
[x,y1,x2,y2]
69
return
path
70
else
:
#
到达不了,上下转弯,递归
71
hasReachPoint[y1
*
self.MaxWidth
+
x]
+=
1
72
p
=
self.IsNTurnReachable(x,y1,x2,y2,path
+
[x,y1],n
-
1
,False,hasReachPoint)
73
if
p
!=
False:
74
return
p
75
else
:
76
break
77
else
:
#
上下移动
78
for
y
in
xrange(y1
-
1
,
-
1
,
-
1
):
#
向上
79
if
self.GetArrayXY(x1,y)
==
0
and
hasReachPoint[y
*
self.MaxWidth
+
x1]
<
n:
80
if
self.IsLineable(x1,y,x2,y2,
1
)
or
self.IsLineable(x1,y,x2,y2,
2
):
81
path
+=
[x1,y,x2,y2]
82
return
path
83
else
:
#
到达不了,左右转弯,递归
84
hasReachPoint[y
*
self.MaxWidth
+
x1]
+=
1
85
p
=
self.IsNTurnReachable(x1,y,x2,y2,path
+
[x1,y],n
-
1
,True,hasReachPoint)
86
if
p
!=
False:
87
return
p
88
else
:
89
break
90
for
y
in
xrange(y1
+
1
,self.MaxHeight):
#
向下
91
if
self.GetArrayXY(x1,y)
==
0
and
hasReachPoint[y
*
self.MaxWidth
+
x1]
<
n:
92
if
self.IsLineable(x1,y,x2,y2,
1
)
or
self.IsLineable(x1,y,x2,y2,
2
):
93
path
+=
[x1,y,x2,y2]
94
return
path
95
else
:
#
到达不了,左右转弯,递归
96
hasReachPoint[y
*
self.MaxWidth
+
x1]
+=
1
97
p
=
self.IsNTurnReachable(x1,y,x2,y2,path
+
[x1,y],n
-
1
,True,hasReachPoint)
98
if
p
!=
False:
99
return
p
100
else
:
101
break
102
return
False
103
#
--------------------------------------------------------
104
def
IsLinkAble(self,x1,y1,x2,y2,n):
#
n连看的计算函数
105
if
n
<=
0:
106
return
False
107
hasReachPoint
=
[0]
*
(self.MaxWidth
*
self.MaxHeight)
108
for
i
in
[0,
1
,
2
,
3
]:
109
if
self.isLineable(x1,y1,x2,y2,i):
110
path
=
[x1,y1,x2,y2]
111
return
path
112
path
=
[x1,y1]
113
p
=
self.IsNTurnReachalbe(x1,y1,x2,y2,path,n
-
1
,False,hasReachPoint)
114
if
p:
115
return
p
116
p
=
self.IsNTurnReachalbe(x1,y1,x2,y2,path,n
-
1
,True,hasReachPoint)
117
if
p:
118
return
p
119
return
False
当然,现在想到还有可以继续优化的地方,例如寻路时,从起点和目标点同时出发寻路,而不是只从一个点出发寻路。这样做或许还可以双线程优化,不过具体做法就没有细想了。
posted on 2009-06-28 19:50
陈昱(CY)
阅读(1586)
评论(2)
编辑
收藏
引用
所属分类:
算法
FeedBack:
#
re: 以前写的一个N连看 2009-06-29 23:15
小卒
我最近想写个立体数独,不过理论功底不行……
回复
更多评论
#
re: 以前写的一个N连看
2009-06-30 09:34
CY
那还要先证明立体数独需要用多少个候选数
回复
更多评论
刷新评论列表
只有注册用户
登录
后才能发表评论。
【推荐】100%开源!大型工业跨平台软件C++源码提供,建模,组态!
相关文章:
某人水题一道
shader的小奏鸣曲
一个想法,实习n维立方体!!! (结束)
一个想法,实现n维超级立方体!!!初步成功!!!(第二章)
一个想法,用程序画出高维超立方体在三维上的投影!!!(1)
以前写的一个N连看
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理