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

简单代码

寻找代码的灵魂

 
 
 

日志

 
 
关于我

对于本博客内所有原创文章和代码的引用必须标明“来源:http://simplesource.blog.163.com/”。如需应用于商业目的必须经本人同意,本人对所有原创文章和代码保留一切权利。 PS:需要部分程序源代码的请留下邮箱地址

网易考拉推荐

求解关灯游戏  

2009-09-13 19:50:39|  分类: 我的程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

   手机上的游戏:有n×m个格子代表n×m个房间,每个房间有一盏灯和一个奇怪的开关,这个开关可以同时控制本房间和上下左右四个房间的灯,但是每次只能同时变换状态,把开的关掉,关的开启。现在有若干个房间的灯开着,问如何使用这些开关关掉所有灯。
  注意到灯的状态跟开关数量有关,但是跟开关使用的次序没有关系,而且某个开关使用两次跟没有使用的效果相同,也就是说n×m个房间最多需要使用n×m次开关就能够把所有灯关掉,每个开关最多使用一次。
  本人愚钝,只想到蛮力搜索的方法,后来在网上找到了一个牛B的算法:用线性代数的方法去求解。具体方法如下:
……吧上面的矩阵看成一个m*n的向量X=(x1,x2,...,x(m*n))
  对于位置k上的开关,它将变化最多5个位置的开关,对应一个向量
C(k)=(0,0,...,1,0,....,1,...,0)
  其中开关状态改变的位置为1,开关状态不改变的位置为0
对于初始向量X=(x1,x2,...,x(m*n)),使用了开关C(k)后,状态会变成
X+C(k) (mod 2)
  所以对初始向量X,我们需要选择一系列的k1,k2,...,ks使得
X+C(k1)+C(k2)+....+C(ks) (mod 2)=O=(0,0,0,...,0)
  我们可以同样构造一个0,1向量Y,使得,如果位置k出现在k1,k2,...ks中,那么Y
在位置k的值是1,不然是0,这样,我们就可以将上面公式写成矩阵形式
X+Y*C (mod 2)=O
  其中C=(C(1)' C(2)' .... C(m*n)')'
  也就是C是由这m*n个行向量构成的矩阵,第k行就是向量C(k)
  最二阶域上,加和减是相同的,也就是上面的方程等价于
Y*C (mod 2)=X
  其中C,X已知,求Y.
  由于(mod 2)运算是一个域 (关于乘除加减封闭,加减是mod 2加减,还满足结合率,交换率)
所以我们可以直接在二阶域上用高斯消元法求解(注意加减是mod 2的,对应计算机上的异或运算)
其中,如果C可逆,解是唯一的,如果C不可逆,解可能不存在,也可能不唯一。
  可以使用追逐法求解,时间复杂度可以只有O(n^3).……
引用自http://blog.csdn.net/mathe/archive/2006/08/30/1143634.aspx lkrich7 (晚上睡不着,白天醒不了)的文章
  根据上述原理写了下面这个程序:
 求解关灯游戏 - 简单代码 - 简单代码

  右键点击格子可以设置灯的状态

求解关灯游戏 - 简单代码 - 简单代码

  双击某个格子可以把这个格子禁用,这样既不能点击该格子来控制灯,也不用关心这个格子中灯的状态(适合解网上的一种小孩起立游戏,还有一种肯德基盛盘子的游戏)

求解关灯游戏 - 简单代码 - 简单代码

  点击反相按钮可以把所有灯的状态反相

求解关灯游戏 - 简单代码 - 简单代码

  点击“蛮力搜索”或者“代数求解”,进行求解,找到解以后小圆点标出的是需要点击的格子。

求解关灯游戏 - 简单代码 - 简单代码
  你可以左键点击这些小圆点验证一下。 

  蛮力搜索用的是递归函数,对于5×5的网格,搜索到解平均需要5-10秒,再大点就慢的无法忍受了。而代数求解只需要一瞬间就可以求解(每次求解相当于一次矩阵与向量的乘法)。由此可见线性代数真是牛B!
程序及源代码下载

 求解关灯.rar   

请用visual studio 2003打开工程

  评论这张
 
阅读(5092)| 评论(6)
推荐 转载

历史上的今天

评论

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

页脚

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