Impossible is Nothing !
如果我QQ上线但又没有给你发消息. 那请你原谅 因为我那时候正专心于我的事业中. 但这并不代表我没有把你放在第一位 恰恰因为我把你放在了第一位 所以才利用没有和你在一起的时间做完我该做的事. 而当我们在一起的时候. 我才能全心全意地和你在一起
posts - 17,comments - 0,trackbacks - 0
分治法一题.


Triomino 拼图:
  Triomino 是由棋盘上的三个邻接的方块组成L型的瓦片.我们的问题是如何用Triomino腐败一个缺少了一个方块
(可以在棋盘的任意位置)的棋盘(2^n x 2^n) .除了这个确实的方块.Triomino 应该覆盖棋盘上所有其他的方块.
而且不能有重叠.


今天刚看算法没多久. 居然就出了这么一个让人摸不着头脑的.
起初一点头绪都没有.于是和朋友一起想. 朋友的提示让我茅塞顿开.

-----------------
    #
    ##

    2x2  L
-----------------
    AA
    AD
    BDDC
    BBCC

    4x4 (三个L型2x2的组成)  L
-----------------
   ....... 

因此. 当我们拿到一个 2^n x 2^n 的时候 我们应该先找出那个空格所在的区块
(均分为4块. 必将落于一中. 没快为 2^(n-1) x 2^(n-1) 


      A | B
      --|--
      C | D

假设落于B. 则我们可以将A C D 用 2^(n-2) 的L型来实现). 然后再对B进行同样的步骤.这样分下去直到分到一个2x2的.
 最后填入一个2x2的L型便实现

posted on 2006-04-04 21:25 kinns 阅读(368) 评论(0)  编辑 收藏 引用 所属分类: Data Structure
只有注册用户登录后才能发表评论。