、（棋盘问题覆盖问题）在一个2k×2 k个...
点击联系发帖人
时间：2011-08-25 11:37
君，已阅读到文档的结尾了呢~~
棋盘覆盖 棋盘覆盖问题实验报告 棋盘覆盖问题 c语言 棋盘问题 棋盘覆盖问题 pascal 棋盘覆盖问题java 棋盘覆盖算法 棋盘覆盖代码 顶点覆盖问题 区间覆盖问题
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
棋盘覆盖问题
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口博客访问： 1008877
博文数量： 267
博客积分： 1305
博客等级： 军士长
技术积分： 4548
注册时间：
不懂的东西还有很多，随着不断的学习，不懂的东西更多，无法消灭更多不懂的东西，那就不断的充实自己吧。
IT168企业级官微
微信号：IT168qiye
系统架构师大会
微信号：SACC2013
分类： C/C++
（一）原理介绍
&&&&在一个2^k * 2^k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为以特殊棋盘。
& & 在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格之外的所有方格，且任何2个L型骨牌不得重叠覆盖。
& & 当k>0时，将2^k * 2^k棋盘分割为4个2^(k-1) * 2^(k - 1)子棋盘，如下图所示。特殊方格必位于4个较小子棋盘之一种，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如下图所示。从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘1*1。
& & 为了更加清楚了解这个原理，下面引用：/2008/04/chessboard_cover.html
& & 这里我们用分治法解决该问题。分治法是把一个规模很大的问题分解为多个规模较小的类似的子问题，然后递归地解决所有子问题，最后再由子问题的解决得到原问题的解决。
& & 【解题思路】
& & 将2^k * 2^k的棋盘，先分成相等的四块子棋盘，其中特殊方格位于四个中的一个，构造剩下没特殊方格的三个字棋盘，将它们中的也假设一个方格为特殊方格。如果是：
& & 左上角的子棋盘（若不存在特殊方格）：则将该子棋盘右下角的那个方格假设为特殊方格；
& & 右上角的子棋盘（若不存在特殊方格）：则将该子棋盘左下角的那个方格假设为特殊方格；
& & 左下角的子棋盘（若不存在特殊方格）：则将该子棋盘右上角的那个方格假设为特殊方格；
& & 右下角的子棋盘（若不存在特殊方格）：则将该子棋盘左上角的那个方格假设为特殊方格；
& & 当然，上面四种情况，只可能且必定只有三种成立，那三个假设的特殊方格刚好构成一个L型骨牌，我们可以给它们作上相同的标志。这样四个子棋盘就分别都和原来的大棋盘类似，我们就可以用递归的算法解决了。
& & 感谢作者哈。
（二）代码实现
#include <stdio.h>
#include <stdlib.h>
#define SIZE 4
static int title = 1;&&&&//title表示L型骨牌的编号
static int board[SIZE][SIZE];
&* 功能：棋盘覆盖
&* @param tr表示棋盘左上角行号
&* @param tc表示棋盘左上角列号
&* @param dr表示特殊棋盘的行号
&* @param dc表示特殊棋盘的列号
&* @param size = 2^k
&* 棋盘的规格为2^k * 2^k
&void ChessBoard(int tr, int tc, int dr, int dc, int size)
&&&& if(1 == size)
&&&&&&&& return;
&&&& int t = title++;&&&&//L型骨牌号
&&&& int s = size / 2;&&&&//分割棋盘
&&&& //覆盖左上角子棋盘
&&&& if(dr < tr + s && dc < tc + s)
&&&&&&&& //特殊方格在此棋盘中
&&&&&&&& ChessBoard(tr, tc, dr, dc, s);
&&&&&&&& //此棋盘无特殊方格
&&&&&&&& //用t号L型骨牌覆盖右下角
&&&&&&&& board[tr + s - 1][tc + s - 1] = t;
&&&&&&&& //覆盖其余方格
&&&&&&&& ChessBoard(tr, tc, tr + s - 1, tc + s - 1, s);
&&&& //覆盖右上角
&&&& if(dr < tr + s && dc >= tc + s)
&&&&&&&& //特殊方格在此棋盘中
&&&&&&&& ChessBoard(tr, tc + s, dr, dc, s);
&&&&&&&& //此子棋盘中无特殊方格
&&&&&&&& //用t号L型骨牌覆盖左下角
&&&&&&&& board[tr + s - 1][tc + s] = t;
&&&&&&&& //覆盖其余方格
&&&&&&&& ChessBoard(tr, tc + s, tr + s - 1, tc + s, s);
&&&& //覆盖左下角子棋盘
&&&& if(dr >= tr + s && dc < tc + s)
&&&&&&&& //特殊方格在此棋盘中
&&&&&&&& ChessBoard(tr + s, tc, dr, dc, s);
&&&&&&&& //用t号L型骨牌覆盖右上角
&&&&&&&& board[tr + s][tc + s -1] = t;
&&&&&&&& //覆盖其余方格
&&&&&&&& ChessBoard(tr + s, tc, tr + s, tc + s - 1, s);
&&&& //覆盖右下角子棋盘
&&&& if(dr >= tr + s && dc >= tc + s)
&&&&&&&& //特殊方格在此棋盘中
&&&&&&&& ChessBoard(tr + s, tc + s, dr, dc, s);
&&&&&&&& //用t号L型骨牌覆盖左上角
&&&&&&&& board[tr + s][tc + s] = t;
&&&&&&&& //覆盖其余方格
&&&&&&&& ChessBoard(tr + s, tc + s, tr + s, tc + s, s);
void ChessPrint()
&&&&int i;
&&&&int j;
&&&&for(i = 0; i < SIZE; i++)
&&&&&&&&for(j = 0; j < SIZE; j++)
&&&&&&&&&&&&printf("%d
", board[i][j]);
&&&&&&&&printf("n");
int main(int argc, char **argv)
&&&&//方便测试，假设特殊方格位置在第三行第三列
&&&&ChessBoard(0, 0, 2, 2, SIZE);
&&&&ChessPrint();
&&&&return 0;
& & 测试结果如下所示。
& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & 梦醒潇湘love
& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & && 16:27
阅读(3668) | 评论(0) | 转发(2) |
相关热门文章
给主人留下些什么吧！~~
请登录后评论。博客访问： 4997
博文数量： 4
博客积分： 0
博客等级： 民兵
技术积分： 30
注册时间：
IT168企业级官微
微信号：IT168qiye
系统架构师大会
微信号：SACC2013
分类： C/C++
原文地址： 作者：
（一）原理介绍
&&&&在一个2^k * 2^k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为以特殊棋盘。
& & 在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格之外的所有方格，且任何2个L型骨牌不得重叠覆盖。
& & 当k>0时，将2^k * 2^k棋盘分割为4个2^(k-1) * 2^(k - 1)子棋盘，如下图所示。特殊方格必位于4个较小子棋盘之一种，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如下图所示。从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘1*1。
& & 为了更加清楚了解这个原理，下面引用：/2008/04/chessboard_cover.html
& & 这里我们用分治法解决该问题。分治法是把一个规模很大的问题分解为多个规模较小的类似的子问题，然后递归地解决所有子问题，最后再由子问题的解决得到原问题的解决。
& & 【解题思路】
& & 将2^k * 2^k的棋盘，先分成相等的四块子棋盘，其中特殊方格位于四个中的一个，构造剩下没特殊方格的三个字棋盘，将它们中的也假设一个方格为特殊方格。如果是：
& & 左上角的子棋盘（若不存在特殊方格）：则将该子棋盘右下角的那个方格假设为特殊方格；
& & 右上角的子棋盘（若不存在特殊方格）：则将该子棋盘左下角的那个方格假设为特殊方格；
& & 左下角的子棋盘（若不存在特殊方格）：则将该子棋盘右上角的那个方格假设为特殊方格；
& & 右下角的子棋盘（若不存在特殊方格）：则将该子棋盘左上角的那个方格假设为特殊方格；
& & 当然，上面四种情况，只可能且必定只有三种成立，那三个假设的特殊方格刚好构成一个L型骨牌，我们可以给它们作上相同的标志。这样四个子棋盘就分别都和原来的大棋盘类似，我们就可以用递归的算法解决了。
& & 感谢作者哈。
（二）代码实现
#include <stdio.h>
#include <stdlib.h>
#define SIZE 4
static int title = 1;&&&&//title表示L型骨牌的编号
static int board[SIZE][SIZE];
&* 功能：棋盘覆盖
&* @param tr表示棋盘左上角行号
&* @param tc表示棋盘左上角列号
&* @param dr表示特殊棋盘的行号
&* @param dc表示特殊棋盘的列号
&* @param size = 2^k
&* 棋盘的规格为2^k * 2^k
&void ChessBoard(int tr, int tc, int dr, int dc, int size)
&&&& if(1 == size)
&&&&&&&& return;
&&&& int t = title++;&&&&//L型骨牌号
&&&& int s = size / 2;&&&&//分割棋盘
&&&& //覆盖左上角子棋盘
&&&& if(dr < tr + s && dc < tc + s)
&&&&&&&& //特殊方格在此棋盘中
&&&&&&&& ChessBoard(tr, tc, dr, dc, s);
&&&&&&&& //此棋盘无特殊方格
&&&&&&&& //用t号L型骨牌覆盖右下角
&&&&&&&& board[tr + s - 1][tc + s - 1] = t;
&&&&&&&& //覆盖其余方格
&&&&&&&& ChessBoard(tr, tc, tr + s - 1, tc + s - 1, s);
&&&& //覆盖右上角
&&&& if(dr < tr + s && dc >= tc + s)
&&&&&&&& //特殊方格在此棋盘中
&&&&&&&& ChessBoard(tr, tc + s, dr, dc, s);
&&&&&&&& //此子棋盘中无特殊方格
&&&&&&&& //用t号L型骨牌覆盖左下角
&&&&&&&& board[tr + s - 1][tc + s] = t;
&&&&&&&& //覆盖其余方格
&&&&&&&& ChessBoard(tr, tc + s, tr + s - 1, tc + s, s);
&&&& //覆盖左下角子棋盘
&&&& if(dr >= tr + s && dc < tc + s)
&&&&&&&& //特殊方格在此棋盘中
&&&&&&&& ChessBoard(tr + s, tc, dr, dc, s);
&&&&&&&& //用t号L型骨牌覆盖右上角
&&&&&&&& board[tr + s][tc + s -1] = t;
&&&&&&&& //覆盖其余方格
&&&&&&&& ChessBoard(tr + s, tc, tr + s, tc + s - 1, s);
&&&& //覆盖右下角子棋盘
&&&& if(dr >= tr + s && dc >= tc + s)
&&&&&&&& //特殊方格在此棋盘中
&&&&&&&& ChessBoard(tr + s, tc + s, dr, dc, s);
&&&&&&&& //用t号L型骨牌覆盖左上角
&&&&&&&& board[tr + s][tc + s] = t;
&&&&&&&& //覆盖其余方格
&&&&&&&& ChessBoard(tr + s, tc + s, tr + s, tc + s, s);
void ChessPrint()
&&&&int i;
&&&&int j;
&&&&for(i = 0; i < SIZE; i++)
&&&&&&&&for(j = 0; j < SIZE; j++)
&&&&&&&&&&&&printf("%d
", board[i][j]);
&&&&&&&&printf("n");
int main(int argc, char **argv)
&&&&//方便测试，假设特殊方格位置在第三行第三列
&&&&ChessBoard(0, 0, 2, 2, SIZE);
&&&&ChessPrint();
&&&&return 0;
& & 测试结果如下所示。
& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & 梦醒潇湘love
& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & && 16:27
阅读(113) | 评论(0) | 转发(0) |
下一篇：没有了
相关热门文章
给主人留下些什么吧！~~
请登录后评论。C/C++程序设计（11）
数据结构与算法（3）
参考：/blog/559388
在一个2^k x 2^k 个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。
这里我们用分治法解决该问题。分治法是把一个规模很大的问题分解为多个规模较小、类似的子问题，然后递归地解决所有子问题，最后再由子问题的解决得到原问题的解决。
【解题思路】：将2^k x 2^k的棋盘，先分成相等的四块子棋盘，其中特殊方格位于四个中的一个，构造剩下没特殊方格三个子棋盘，将他们中的也假一个方格设为特殊方格。如果是：
左上的子棋盘（若不存在特殊方格）----则将该子棋盘右下角的那个方格假设为特殊方格
右上的子棋盘（若不存在特殊方格）----则将该子棋盘左下角的那个方格假设为特殊方格
左下的子棋盘（若不存在特殊方格）----则将该子棋盘右上角的那个方格假设为特殊方格
右下的子棋盘（若不存在特殊方格）----则将该子棋盘左上角的那个方格假设为特殊方格
当然上面四种，只可能且必定只有三个成立，那三个假设的特殊方格刚好构成一个L型骨架，我们可以给它们作上相同的标记。这样四个子棋盘就分别都和原来的大棋盘类似，我们就可以用递归算法解决。
(tr,tc) -- 当前棋盘左上角坐标
(dr,dc) -- 黑色方格所在位置
size：当前棋盘的大小:2^k
#include &iostream&
#include &cstdio&
int tile = 1;//L型骨牌的编号(递增)
int board[100][100];//棋盘
void chessBoard(int tr, int tc, int dr, int dc, int size)
if(size == 1)//棋盘方格大小为1,说明递归到最里层
int t = tile++;//每次递增1
int s = size / 2;//棋盘中间的行、列号(相等的)
//检查特殊方块是否在左上角子棋盘中
if(dr & tr + s && dc & tc + s) chessBoard(tr, tc, dr, dc, s);//在,递归寻找子棋盘
else//不在，将该子棋盘右下角的方块视为特殊方块
board[tr+s-1][tc+s-1] =//左上角子棋盘的右下角方块
chessBoard(tr, tc, tr+s-1, tc+s-1, s);
//检查特殊方块是否在右上角子棋盘中
if(dr & tr + s && dc &= tc + s) chessBoard(tr, tc+s, dr, dc, s);
else//不在，将该子棋盘左下角的方块视为特殊方块
board[tr+s-1][tc+s] =//右上角棋盘的左下角方块
chessBoard(tr, tc+s, tr+s-1, tc+s, s);
//检查特殊方块是否在左下角子棋盘中
if(dr &= tr + s && dc & tc + s) chessBoard(tr+s, tc, dr, dc, s);
//不在，将该子棋盘右上角的方块视为特殊方块
board[tr+s][tc+s-1] =
chessBoard(tr+s, tc, tr+s, tc+s-1, s);
//检查特殊方块是否在右下角子棋盘中
if(dr &= tr + s && dc &= tc + s) chessBoard(tr+s, tc+s, dr, dc, s);
//不在，将该子棋盘左上角的方块视为特殊方块
board[tr+s][tc+s] =//右下角棋盘的左上角
chessBoard(tr+s, tc+s, tr+s, tc+s, s);
int main()
#ifndef ONLINE_JUDGE
freopen(&in.txt&,&r&,stdin);
freopen(&out.txt&,&w&,stdout);
#endif // ONLINE_JUDGE
cout && &输入棋盘的size(大小必须是2的n次幂): &;
int index_x,index_y;
cout && &输入特殊方格位置的坐标: &;
cin && index_x && index_y;
chessBoard(0,0,index_x,index_y,size);
for(int i = 0; i & i++)
for(int j = 0; j & j++)
cout && board[i][j] && &\t&;
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：4456次
排名：千里之外
原创：20篇
(4)(4)(1)(2)(8)(7)}
棋盘覆盖 棋盘覆盖问题实验报告 棋盘覆盖问题 c语言 棋盘问题 棋盘覆盖问题 pascal 棋盘覆盖问题java 棋盘覆盖算法 棋盘覆盖代码 顶点覆盖问题 区间覆盖问题
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
棋盘覆盖问题
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口博客访问： 1008877
博文数量： 267
博客积分： 1305
博客等级： 军士长
技术积分： 4548
注册时间：
不懂的东西还有很多，随着不断的学习，不懂的东西更多，无法消灭更多不懂的东西，那就不断的充实自己吧。
IT168企业级官微
微信号：IT168qiye
系统架构师大会
微信号：SACC2013
分类： C/C++
（一）原理介绍
&&&&在一个2^k * 2^k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为以特殊棋盘。
& & 在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格之外的所有方格，且任何2个L型骨牌不得重叠覆盖。
& & 当k>0时，将2^k * 2^k棋盘分割为4个2^(k-1) * 2^(k - 1)子棋盘，如下图所示。特殊方格必位于4个较小子棋盘之一种，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如下图所示。从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘1*1。
& & 为了更加清楚了解这个原理，下面引用：/2008/04/chessboard_cover.html
& & 这里我们用分治法解决该问题。分治法是把一个规模很大的问题分解为多个规模较小的类似的子问题，然后递归地解决所有子问题，最后再由子问题的解决得到原问题的解决。
& & 【解题思路】
& & 将2^k * 2^k的棋盘，先分成相等的四块子棋盘，其中特殊方格位于四个中的一个，构造剩下没特殊方格的三个字棋盘，将它们中的也假设一个方格为特殊方格。如果是：
& & 左上角的子棋盘（若不存在特殊方格）：则将该子棋盘右下角的那个方格假设为特殊方格；
& & 右上角的子棋盘（若不存在特殊方格）：则将该子棋盘左下角的那个方格假设为特殊方格；
& & 左下角的子棋盘（若不存在特殊方格）：则将该子棋盘右上角的那个方格假设为特殊方格；
& & 右下角的子棋盘（若不存在特殊方格）：则将该子棋盘左上角的那个方格假设为特殊方格；
& & 当然，上面四种情况，只可能且必定只有三种成立，那三个假设的特殊方格刚好构成一个L型骨牌，我们可以给它们作上相同的标志。这样四个子棋盘就分别都和原来的大棋盘类似，我们就可以用递归的算法解决了。
& & 感谢作者哈。
（二）代码实现
#include <stdio.h>
#include <stdlib.h>
#define SIZE 4
static int title = 1;&&&&//title表示L型骨牌的编号
static int board[SIZE][SIZE];
&* 功能：棋盘覆盖
&* @param tr表示棋盘左上角行号
&* @param tc表示棋盘左上角列号
&* @param dr表示特殊棋盘的行号
&* @param dc表示特殊棋盘的列号
&* @param size = 2^k
&* 棋盘的规格为2^k * 2^k
&void ChessBoard(int tr, int tc, int dr, int dc, int size)
&&&& if(1 == size)
&&&&&&&& return;
&&&& int t = title++;&&&&//L型骨牌号
&&&& int s = size / 2;&&&&//分割棋盘
&&&& //覆盖左上角子棋盘
&&&& if(dr < tr + s && dc < tc + s)
&&&&&&&& //特殊方格在此棋盘中
&&&&&&&& ChessBoard(tr, tc, dr, dc, s);
&&&&&&&& //此棋盘无特殊方格
&&&&&&&& //用t号L型骨牌覆盖右下角
&&&&&&&& board[tr + s - 1][tc + s - 1] = t;
&&&&&&&& //覆盖其余方格
&&&&&&&& ChessBoard(tr, tc, tr + s - 1, tc + s - 1, s);
&&&& //覆盖右上角
&&&& if(dr < tr + s && dc >= tc + s)
&&&&&&&& //特殊方格在此棋盘中
&&&&&&&& ChessBoard(tr, tc + s, dr, dc, s);
&&&&&&&& //此子棋盘中无特殊方格
&&&&&&&& //用t号L型骨牌覆盖左下角
&&&&&&&& board[tr + s - 1][tc + s] = t;
&&&&&&&& //覆盖其余方格
&&&&&&&& ChessBoard(tr, tc + s, tr + s - 1, tc + s, s);
&&&& //覆盖左下角子棋盘
&&&& if(dr >= tr + s && dc < tc + s)
&&&&&&&& //特殊方格在此棋盘中
&&&&&&&& ChessBoard(tr + s, tc, dr, dc, s);
&&&&&&&& //用t号L型骨牌覆盖右上角
&&&&&&&& board[tr + s][tc + s -1] = t;
&&&&&&&& //覆盖其余方格
&&&&&&&& ChessBoard(tr + s, tc, tr + s, tc + s - 1, s);
&&&& //覆盖右下角子棋盘
&&&& if(dr >= tr + s && dc >= tc + s)
&&&&&&&& //特殊方格在此棋盘中
&&&&&&&& ChessBoard(tr + s, tc + s, dr, dc, s);
&&&&&&&& //用t号L型骨牌覆盖左上角
&&&&&&&& board[tr + s][tc + s] = t;
&&&&&&&& //覆盖其余方格
&&&&&&&& ChessBoard(tr + s, tc + s, tr + s, tc + s, s);
void ChessPrint()
&&&&int i;
&&&&int j;
&&&&for(i = 0; i < SIZE; i++)
&&&&&&&&for(j = 0; j < SIZE; j++)
&&&&&&&&&&&&printf("%d
", board[i][j]);
&&&&&&&&printf("n");
int main(int argc, char **argv)
&&&&//方便测试，假设特殊方格位置在第三行第三列
&&&&ChessBoard(0, 0, 2, 2, SIZE);
&&&&ChessPrint();
&&&&return 0;
& & 测试结果如下所示。
& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & 梦醒潇湘love
& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & && 16:27
阅读(3668) | 评论(0) | 转发(2) |
相关热门文章
给主人留下些什么吧！~~
请登录后评论。博客访问： 4997
博文数量： 4
博客积分： 0
博客等级： 民兵
技术积分： 30
注册时间：
IT168企业级官微
微信号：IT168qiye
系统架构师大会
微信号：SACC2013
分类： C/C++
原文地址： 作者：
（一）原理介绍
&&&&在一个2^k * 2^k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为以特殊棋盘。
& & 在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格之外的所有方格，且任何2个L型骨牌不得重叠覆盖。
& & 当k>0时，将2^k * 2^k棋盘分割为4个2^(k-1) * 2^(k - 1)子棋盘，如下图所示。特殊方格必位于4个较小子棋盘之一种，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如下图所示。从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘1*1。
& & 为了更加清楚了解这个原理，下面引用：/2008/04/chessboard_cover.html
& & 这里我们用分治法解决该问题。分治法是把一个规模很大的问题分解为多个规模较小的类似的子问题，然后递归地解决所有子问题，最后再由子问题的解决得到原问题的解决。
& & 【解题思路】
& & 将2^k * 2^k的棋盘，先分成相等的四块子棋盘，其中特殊方格位于四个中的一个，构造剩下没特殊方格的三个字棋盘，将它们中的也假设一个方格为特殊方格。如果是：
& & 左上角的子棋盘（若不存在特殊方格）：则将该子棋盘右下角的那个方格假设为特殊方格；
& & 右上角的子棋盘（若不存在特殊方格）：则将该子棋盘左下角的那个方格假设为特殊方格；
& & 左下角的子棋盘（若不存在特殊方格）：则将该子棋盘右上角的那个方格假设为特殊方格；
& & 右下角的子棋盘（若不存在特殊方格）：则将该子棋盘左上角的那个方格假设为特殊方格；
& & 当然，上面四种情况，只可能且必定只有三种成立，那三个假设的特殊方格刚好构成一个L型骨牌，我们可以给它们作上相同的标志。这样四个子棋盘就分别都和原来的大棋盘类似，我们就可以用递归的算法解决了。
& & 感谢作者哈。
（二）代码实现
#include <stdio.h>
#include <stdlib.h>
#define SIZE 4
static int title = 1;&&&&//title表示L型骨牌的编号
static int board[SIZE][SIZE];
&* 功能：棋盘覆盖
&* @param tr表示棋盘左上角行号
&* @param tc表示棋盘左上角列号
&* @param dr表示特殊棋盘的行号
&* @param dc表示特殊棋盘的列号
&* @param size = 2^k
&* 棋盘的规格为2^k * 2^k
&void ChessBoard(int tr, int tc, int dr, int dc, int size)
&&&& if(1 == size)
&&&&&&&& return;
&&&& int t = title++;&&&&//L型骨牌号
&&&& int s = size / 2;&&&&//分割棋盘
&&&& //覆盖左上角子棋盘
&&&& if(dr < tr + s && dc < tc + s)
&&&&&&&& //特殊方格在此棋盘中
&&&&&&&& ChessBoard(tr, tc, dr, dc, s);
&&&&&&&& //此棋盘无特殊方格
&&&&&&&& //用t号L型骨牌覆盖右下角
&&&&&&&& board[tr + s - 1][tc + s - 1] = t;
&&&&&&&& //覆盖其余方格
&&&&&&&& ChessBoard(tr, tc, tr + s - 1, tc + s - 1, s);
&&&& //覆盖右上角
&&&& if(dr < tr + s && dc >= tc + s)
&&&&&&&& //特殊方格在此棋盘中
&&&&&&&& ChessBoard(tr, tc + s, dr, dc, s);
&&&&&&&& //此子棋盘中无特殊方格
&&&&&&&& //用t号L型骨牌覆盖左下角
&&&&&&&& board[tr + s - 1][tc + s] = t;
&&&&&&&& //覆盖其余方格
&&&&&&&& ChessBoard(tr, tc + s, tr + s - 1, tc + s, s);
&&&& //覆盖左下角子棋盘
&&&& if(dr >= tr + s && dc < tc + s)
&&&&&&&& //特殊方格在此棋盘中
&&&&&&&& ChessBoard(tr + s, tc, dr, dc, s);
&&&&&&&& //用t号L型骨牌覆盖右上角
&&&&&&&& board[tr + s][tc + s -1] = t;
&&&&&&&& //覆盖其余方格
&&&&&&&& ChessBoard(tr + s, tc, tr + s, tc + s - 1, s);
&&&& //覆盖右下角子棋盘
&&&& if(dr >= tr + s && dc >= tc + s)
&&&&&&&& //特殊方格在此棋盘中
&&&&&&&& ChessBoard(tr + s, tc + s, dr, dc, s);
&&&&&&&& //用t号L型骨牌覆盖左上角
&&&&&&&& board[tr + s][tc + s] = t;
&&&&&&&& //覆盖其余方格
&&&&&&&& ChessBoard(tr + s, tc + s, tr + s, tc + s, s);
void ChessPrint()
&&&&int i;
&&&&int j;
&&&&for(i = 0; i < SIZE; i++)
&&&&&&&&for(j = 0; j < SIZE; j++)
&&&&&&&&&&&&printf("%d
", board[i][j]);
&&&&&&&&printf("n");
int main(int argc, char **argv)
&&&&//方便测试，假设特殊方格位置在第三行第三列
&&&&ChessBoard(0, 0, 2, 2, SIZE);
&&&&ChessPrint();
&&&&return 0;
& & 测试结果如下所示。
& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & 梦醒潇湘love
& & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & & && 16:27
阅读(113) | 评论(0) | 转发(0) |
下一篇：没有了
相关热门文章
给主人留下些什么吧！~~
请登录后评论。C/C++程序设计（11）
数据结构与算法（3）
参考：/blog/559388
在一个2^k x 2^k 个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。
这里我们用分治法解决该问题。分治法是把一个规模很大的问题分解为多个规模较小、类似的子问题，然后递归地解决所有子问题，最后再由子问题的解决得到原问题的解决。
【解题思路】：将2^k x 2^k的棋盘，先分成相等的四块子棋盘，其中特殊方格位于四个中的一个，构造剩下没特殊方格三个子棋盘，将他们中的也假一个方格设为特殊方格。如果是：
左上的子棋盘（若不存在特殊方格）----则将该子棋盘右下角的那个方格假设为特殊方格
右上的子棋盘（若不存在特殊方格）----则将该子棋盘左下角的那个方格假设为特殊方格
左下的子棋盘（若不存在特殊方格）----则将该子棋盘右上角的那个方格假设为特殊方格
右下的子棋盘（若不存在特殊方格）----则将该子棋盘左上角的那个方格假设为特殊方格
当然上面四种，只可能且必定只有三个成立，那三个假设的特殊方格刚好构成一个L型骨架，我们可以给它们作上相同的标记。这样四个子棋盘就分别都和原来的大棋盘类似，我们就可以用递归算法解决。
(tr,tc) -- 当前棋盘左上角坐标
(dr,dc) -- 黑色方格所在位置
size：当前棋盘的大小:2^k
#include &iostream&
#include &cstdio&
int tile = 1;//L型骨牌的编号(递增)
int board[100][100];//棋盘
void chessBoard(int tr, int tc, int dr, int dc, int size)
if(size == 1)//棋盘方格大小为1,说明递归到最里层
int t = tile++;//每次递增1
int s = size / 2;//棋盘中间的行、列号(相等的)
//检查特殊方块是否在左上角子棋盘中
if(dr & tr + s && dc & tc + s) chessBoard(tr, tc, dr, dc, s);//在,递归寻找子棋盘
else//不在，将该子棋盘右下角的方块视为特殊方块
board[tr+s-1][tc+s-1] =//左上角子棋盘的右下角方块
chessBoard(tr, tc, tr+s-1, tc+s-1, s);
//检查特殊方块是否在右上角子棋盘中
if(dr & tr + s && dc &= tc + s) chessBoard(tr, tc+s, dr, dc, s);
else//不在，将该子棋盘左下角的方块视为特殊方块
board[tr+s-1][tc+s] =//右上角棋盘的左下角方块
chessBoard(tr, tc+s, tr+s-1, tc+s, s);
//检查特殊方块是否在左下角子棋盘中
if(dr &= tr + s && dc & tc + s) chessBoard(tr+s, tc, dr, dc, s);
//不在，将该子棋盘右上角的方块视为特殊方块
board[tr+s][tc+s-1] =
chessBoard(tr+s, tc, tr+s, tc+s-1, s);
//检查特殊方块是否在右下角子棋盘中
if(dr &= tr + s && dc &= tc + s) chessBoard(tr+s, tc+s, dr, dc, s);
//不在，将该子棋盘左上角的方块视为特殊方块
board[tr+s][tc+s] =//右下角棋盘的左上角
chessBoard(tr+s, tc+s, tr+s, tc+s, s);
int main()
#ifndef ONLINE_JUDGE
freopen(&in.txt&,&r&,stdin);
freopen(&out.txt&,&w&,stdout);
#endif // ONLINE_JUDGE
cout && &输入棋盘的size(大小必须是2的n次幂): &;
int index_x,index_y;
cout && &输入特殊方格位置的坐标: &;
cin && index_x && index_y;
chessBoard(0,0,index_x,index_y,size);
for(int i = 0; i & i++)
for(int j = 0; j & j++)
cout && board[i][j] && &\t&;
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：4456次
排名：千里之外
原创：20篇
(4)(4)(1)(2)(8)(7)}
我要回帖
更多关于 棋盘覆盖问题 的文章
更多推荐
- ·手机版网易云mv在哪里音乐怎么看mv？
- ·求排名前十小说推荐
- ·谁用过的比较好用滋润公认最好用的身体乳乳推荐下呗？
- ·2013第二届亚洲国际声乐比赛报名大赛第二届亚洲国际歌剧比赛
- ·2017.1.13号12.30男孩命里查孩子五行缺什么么？
- ·高压电机变压器单相接地地保护国家有明文规定吗
- ·注册资产评估师待遇好考吗？都考什么啊？以后...
- ·哪种减肥产品效果好最好 45
- ·学长学姐 我准备为考2012天天向上 汕头大学学...
- ·西门子s7 300-200 电脑怎么连不上PL...
- ·谁有慈溪职高视频英语学习的视频，给我一个
- ·아 51200 50472;직 &#...
- ·听说你有北师大版高中英语必修一单词1和2单词...
- ·(a^2+b^2)(a^2+b^2-3...
- ·A管上端封闭，AB两管用皇家橡皮筋管连通，开...
- ·走出 半命题作文文 如花多好 该怎样写
- ·上大学冬天到底要不要热车参加社团呢？
- ·数学小教一级 如何抓后1/3的学生？
- ·最难做的饭打一成语，最小的针，
- ·宇宙天有边吗吗?
- ·、（棋盘问题覆盖问题）在一个2k×2 k个...
- ·暑假好听的作文集名字的名字、卷首语、卷末语 要原...
- ·在哪里可以学到魔法地道的美语发音呢，我现在...
- ·对最熟悉的陌生人英语腼腆 英语怎么说
- ·请问你被陕西交通职业学院技术学院录取了吗 ...
- ·耐压测试仪低压过电流互感器耐压试验保护如何设定？
- ·我想知道哪个西北大学有机化学学比较出名。有没...
- ·吉大商院会计吉大研究生招生简章的人也太少了 去掉...
- ·采撷阳光 温暖阳光壁纸他人 用英文翻译
- ·在括号里写上沉浮同什么意思相近近的字
- ·作文：有一种声音，什么真使我难忘忘
- ·我高中时病了，现在在家自学会计，想问下有没...
- ·(1/2)【九上历史材料题】阅读材料，回答：明朝...
- ·武汉科技大学武汉城市学院院校学生会怎么进?
- ·好激光焊接技术接
