注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

雨星的博客

淘宝小店小雨时尚女鞋http://rainmmshoes.taobao.com

 
 
 

日志

 
 

华容道攻略解法  

2011-07-13 15:15:20|  分类: 游戏动漫 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
华容道已经被研究过多年,也总结了许多关口的走法,为让各位喜欢华容道的朋友少走弯路,我把一些走法整理出来,与大家分享。     下面的走法沿用L.E.Hordern的记录方法,即在多数情况下只要指明走哪一个棋子就够了,只有少数情况下才指明如何走。这时用以下符号来表示。L向左;R向右;U向上;D向下;!只走一格;#必须拐弯(指最小棋子)。没有这些符号时,表示直走,到头为止(一格或两格)。棋子编号见图1。当然,这只是指出了如何过关,大家也不必死记硬背这些步骤,关键要从此研究出过关的必要条件,而达到通关的目的。     
(1) 横竖皆将     
6 4 5 7 # 9 6 8 3 5 7 9 L 2 A 7 5 1 7 L A 2 4 5 9 L 4 5 8#3 1 9 L 4 5 8#3 1 9 L 4 5# 2A 9 # 4 1 3 6 8 5 2 A 9 7 4 3 5 8 6 D 3 A 9 1 7 4 3 1 2 2 6R 5# 8# A 9 1 7 4 3 1 A 9 1 7 2 6 8 5 A 9 3 4 2 6 5 # A     
(2)守口如瓶之一     
5 7L 2 A 1 3 6 4 1 A 2 7# 9 8 4 1 6 #4 1 6 5 #7 9 5 6 #1 4 7 # 9 5#2 A 7 #9 4 1 8 6 D 5 2 A 7 3 9 1 5 6 7 1 4 D 1 A 7 1 3 9 1 4 2 8 R 5 #6#A 7 1 3 9 1 4 A 8 3 2 8 6 5 A 7 1 9 2 8 5#A     
(3)守口如瓶之二     
7#9 8 6 #3 1 A 2 4 7 R 2 A 1 3 6 #8 9 7#4 A 5 6 #8 9 7 # 8 9 3 6# 51 6 U 5 1 A 4 81 2U 8 1 1 7 9 3 5 2#8 7 # 4 A 2#8 5 3 9 1 7 4 A 2 6 8 3 7 1 9 5 D 3 9 2 1 6 8 3 5 4 9 R 1# 7# A 2 1 6 8 3 5 A 2 1 6 4 A 7 1 A 2 3 8 4 9 1#A     
4)层层设防之二     
9 L8#4 2 A 1 3 5 2 4 8 9 6 7 2 5 3 1 L,A 4 5 2 7 6 9 8 2 7 6 # 7 8# 7 9 3 6 # 5 8 #4 A 6# 5 3 8 9 2 4 A 6 1 5 8# A 6 1 1 5 8 3 4 7 2U 9 7 2 A 6 1# 4 A 6 3 2 6# 7 9 A 1#3 2 8 5 3 1 A 9 7 1# A 4 3 2 # A 1 6# 8 A 1 4 3 1# 4 3 9 7 8 6 D A 6 2 1 4 3 9 7 6 8 A 9 7 8 #A     
(5)Top secret     
7 5 3 2 1 4 6 7 L A 1#4 6 7 1 1 3 5 9 8 A 1 4 2 5 3# 4 7 R 6 2 4 1 A 8 9 3 D 5 1 4 2 7 U 6 U A 1 3 9 8 3 D 1 D A 7D 6D 2 5 4 9 8 3 1 A 9 8 1#A     
(6)三军联防     
6 7 4 3 7# 3 4 2 1 A 7 5 8 4 6 9# 6 4 8 3 9 L 2 1 A 5# 3 8 9 U 4 6 2 1 A5 7     3 9# A 1 2 4 6 8 9 A 1 2 4 6 9# A 3 7 5 1 2 4 6 9 8 A 4 6 8#A     
(7)堵塞要道     
5 9 6 7 4#2 A 3 #7 5 6 9 8 4 2 D A 3 1 7 5 6 9 8 4 2 D A 1 3 D 7 5 6 9 8 4 2 A 9 8 2#A     
(8)水泄不通     
9 7 6 8 9 U 7 6 5 4 8 9 U 5 4 9 A 1 3# 8 A 1 2 9 1# 4 5 A 3# 21# 4 5 6 7 A 5 4 1# 2 3 #5 4 2 1 9 D 3 8 5 4 A 7 6 1# 9 3 8#5 4 A 1 9 6 7 1 9 D A 4 5 2 8 3 U 6 7 9 1 A 6 7 1#A     
(9)四路进兵(原文 67步,11 66步)     
A 4 3 #2 A 4 3 #1 5 2 #7 6 A 3 #1 2 #7 6 9 8 A 6 7 2 0#1 3 #6 7 1 2 5 D 3 4 6 7 A 8 9 2# 5 3 4# 6 7 A 2 5 9 8 2 5 D A 7 6 1 4 3 U 9 8 5 2 A 9 8 2# A    
         
华容道问题用计算机求解,一般采用广度搜索的方法,其原理很简单,就是把下一步可能有的走法全部算出来,比如第一步有五种走法,将这五种走法的下一步走法分别算出来,可能会有三十步,在继续将这三十步走法的下一步走法分别算出来,可能会更多,以此类推,直到达到目标状态(曹操在出口位置)为止。     在解华容道的问题上,我觉得有两个问题比较棘手。     
其一、算法的效率。     
其二、获得最优解法。     
我是这样解决的:     
1、 要提高算法的效率,首先要知道算法的瓶颈在什么地方,在得出每一个状态(走完一步各个棋子的位置)都要和前面的状态进行比较,以保证不重复,随着步数的增多,状态数会大幅度增加,这是,和前面的状态比较这一过程成了整个算法的效率。解决的办法,从两个地方着手,其一,增加每一步比较的速度。在程序中,用5*4的数组表示一个状态,这样,每一次比较要比较二十个数,因为数组中每个数定义从0-7,用三个二进制位可以表示,3*20=60位,用一个64位数就可以表示(有的资料说用四个字节就可以,我实在想不出来),这样每次比较一个64位数就可以了。其二、减少比较的状态,这是提高效率的关键。比较的时候不要和前面所有的状态都进行比较,只要和前两步的所有状态进行比较就可以了。经过以上的优化,在解横刀立马时,大约需要一,两秒钟就可以了,(我的机器,赛扬1.1OC1.46)。     
2、 获得最优解法,比如横刀立马是81步,这里的一步指移动一个棋子,可以把一个卒子向一个方向移动两格,或者卒子拐弯移动两格,或者一个将向一个方向移动两格(横将横着移,竖将竖着移)都是一步。获得最优解法的关键是把下一步可能有的走法全部算出来,不能遗漏。我是根据空格来算走法的的,分三种情况:     
① 、卒子拐弯移动,如果有连着两个空格(横向的),则如果在它的上面或下面(有四个位置)有卒子的话,那么可以拐弯移动,有四种走法。如果两个空格是竖向的,那么,空格的左右如果有卒子,也可以拐弯移动,也有四种走法。     
②、向一个方向移动两格,这里可能出现的情况有:卒子向一个方向移动两格,横将横着移两格,竖将竖着移两格     
③、考虑向一个方向移动一格的情况,这里情况很多,我不一一列举了。     
以上的算法很麻烦,很大一部分程序用来写这个了,如果大家有更简单的,可以告诉我,但一个原则,必须把所有的走法全部考虑。     
另外,说一下我在写程序时的小插曲。程序快写好时,运行时发现,每解一次,内存使用会增加7,8兆,后来发现分配的内存每释放导致的,其实在函数中也就分配了几十个字节,由于被重复调用,最后泄漏的内存就很可观了,以后使用指针分配内存可要注意了,(C用malloc,C++用new),一定要释放,弄不好,^@^。     
程序用dev-C++ 4.9.9.0(可以从网上下,只有十多兆)编译通过,因为dev C++没有框架等东西,所以界面直接用window API写的。生成的可执行文件很小,68 K。另外,在程序中可以自定义布局,用5*4数表示。其中0-空格,1-卒子,2到6 将,7曹操。
 
本文来源: http://zhidao.baidu.com/question/9729072.html
  评论这张
 
阅读(485)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017