随笔 - 70  文章 - 160  trackbacks - 0

公告:
知识共享许可协议
本博客采用知识共享署名 2.5 中国大陆许可协议进行许可。本博客版权归作者所有,欢迎转载,但未经作者同意不得随机删除文章任何内容,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。 具体操作方式可参考此处。如您有任何疑问或者授权方面的协商,请给我留言。

常用链接

留言簿(8)

随笔档案

文章档案

搜索

  •  

积分与排名

  • 积分 - 176148
  • 排名 - 145

最新评论

阅读排行榜

评论排行榜

虽然这个问题已经在网上被讨论遍了,但是最近从新拾起算法,感觉有必要夯实一下基础。

棋盘覆盖问题
首先大致描述一下题目
在一个2^k×2^k个方格组成的棋盘中,若有一个方格与其他方格不同,则称该方格为一特殊方格,且称该棋盘为一个特殊棋盘.显然特殊方格在棋盘上出现的位置有4^k种情形.因而对任何
k≥0,有4^k种不同的特殊棋盘.
下图–图(1)中的特殊棋盘是当k=2时16个特殊棋盘中的一个:

 

图(1)

题目要求在棋盘覆盖问题中,要用下图—图(2)所示的4种不同形态的L型骨牌覆盖一个给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖.

 

图(2)

思路分析:
当k>0时,将2^k×2^k棋盘分割为4个2^k-1×2^k-1子棋盘,如下图–图(3)所示:


 

图(3)

特殊方格必位于4个较小子棋盘之一中,其余3个子棋盘中无特殊方格.为了将这3个无特殊方格的子棋盘转化为特殊棋盘,可以用一个L型骨牌覆盖这3个较小棋盘的会合处。
如下图–图(4)所示,这3个子棋盘上被L型骨牌覆盖的方格就成为该棋盘上的特殊方格,从而原问题转化为4个较小规模的棋盘覆盖问题.递归地使用这种分割,直至棋盘简化为1×1棋盘。

以下是代码:

 

/*
Author: Tanky Woo
Blog:   www.WuTianQi.com
棋盘覆盖问题
分治法
2010-12-3
*/
#include 
<iostream>
using namespace std;
const int N = 11;
int Board[N][N];
int tile = 0;
 
/*
tr:棋盘左上角方格的行号
tc:棋盘左上角方格的列号
dr:特殊方格所在的行号
dc:特殊方格所在的列号
size:方形棋盘的边长
*/
void ChessBoard(int tr, int tc, int dr, int dc, int size)
{
    
if(size == 1)
        
return;
    
int t = ++tile, s = size/2;
 
    
//覆盖左上角子棋盘
    if(dr<tr+&& dc<tc+s)
        
//特殊方格在此棋盘中
        ChessBoard(tr, tc, dr, dc, s);
    
else   // 此棋盘无特殊方格
    {
        
// 用t号L型骨型牌覆盖右下角
        Board[tr+s-1][tc+s-1= t;
        
// 覆盖其余方格
        ChessBoard(tr, tc, tr+s-1, tc+s-1, s);
    }
 
    
//覆盖右上角子棋盘
    if(dr<tr+&& dc>=tc+s)
        ChessBoard(tr, tc
+s, dr, dc, s);
    
else
    {
        Board[tr
+s-1][tc+s] = t;
        ChessBoard(tr, tc
+s, tr+s-1, tc+s, s);
    }
 
    
//覆盖左下角子棋盘
    if(dr>=tr+&& dc<tc+s)
        ChessBoard(tr
+s, tc, dr, dc, s);
    
else
    {
        Board[tr
+s][tc+s-1= t;
        ChessBoard(tr
+s, tc, tr+s, tc+s-1, s);
    }
 
    
//覆盖右下角子棋盘
    if(dr>=tr+&& dc>=tc+s)
        ChessBoard(tr
+s, tc+s, dr, dc, s);
    
else
    {
        Board[tr
+s][tc+s] = t;
        ChessBoard(tr
+s, tc+s, tr+s, tc+s, s);
    }
}
 
void DisplayBoard(int size)
{
    
for(int i=1; i<=size; ++i)
    {
        
for(int j=1; j<=size; ++j)
            printf(
"%2d ", Board[i][j]);
        printf(
"\n");
    }
}
 
int main()
{
    ChessBoard(
11124);
    DisplayBoard(
4);
    
return 0;
}
posted on 2010-12-08 10:23 Tanky Woo 阅读(3874) 评论(7)  编辑 收藏 引用

FeedBack:
# re: 棋盘覆盖问题 2010-12-08 11:52 tiny
goodjob
  回复  更多评论
  
# re: 棋盘覆盖问题 2010-12-09 00:18 曹小天
这代码是你自己写的吗?我在百度文库上看见《(棋盘覆盖)实验报告》上的代码核心部分和你的一摸一样,你的只不过多了输出 结果罢了。你的问题解析也和那也是字字不差。  回复  更多评论
  
# re: 棋盘覆盖问题 2010-12-13 11:45 crossgate
解决思路很有启发性。困难的问题通过层层分解,最后都成为简单的问题。

  回复  更多评论
  
# re: 棋盘覆盖问题 2010-12-13 11:49 Tanky Woo
@曹小天
你好,无论是你在百度文库上看到的,还是在我这看到的,来源都是王晓东的《计算机算法设计与分析(第3版) 》,不过以上包括代码(图片除外),都是我自己打出来的。  回复  更多评论
  
# re: 棋盘覆盖问题 2011-09-17 15:38 td
如何写动态二维数组?  回复  更多评论
  
# re: 棋盘覆盖问题 2012-03-27 21:22 cclive1601
写的很好,希望多和你交流,谢谢  回复  更多评论
  
# re: 棋盘覆盖问题 2014-04-08 18:19 bauce
你好,请问为什么当棋盘是16*16的时候得不到正确的结果,比如有四相同的数个在一起

当棋盘是32*32的时候,返回值不是0,也就是程序没有正常结束  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理