残缺棋盘完美覆盖 C++
解酒的水果-流星雨歌词
一．问题描述：
残缺棋盘是有一个2
k
x2
k
(k≧1)个方格的棋盘，其中恰有一个方格残缺。
以上为四种三格板，残缺棋盘
问题就是要用这四种三格板覆盖更大的残缺棋盘。在此覆
盖中要求：
（1）两个三个板不能重叠；
（2）三格板不能覆盖残缺方格，但必须覆盖其他所有方格。
二．算法设计：
当k>0时，将2
k
×2
k
棋盘
分割为4个2
k-1
×2
k-1
。特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可
以用一个
L型骨牌覆盖这3个较小棋盘的会合处，从而将原问题转化为4个较小规模的棋
盘覆盖问题。递归地使用
这种分割，直至棋盘简化为棋盘1×1。每次都对分割后的四个小
方块进行判断，判断特殊方格是否在里
面。这里的判断的方法是每次先记录下整个大方块的
左上角方格的行列坐标，然后再与特殊方格坐标进行
比较，就可以知道特殊方格是否在该块
中。如果特殊方块在里面，这直接递归下去求即可，如果不在，这
根据分割的四个方块的
不同位置，把右下角、左下角、右上角或者左上角的方格标记为特殊方块，然后继
续递归。
三．代码实现：
#include
#include
#include
using namespace std;
int tile=0;
int
*(*board) = NULL;定义指向指针的指针用于动态的创建用于存储骨牌号的数组
void chessBoard(int tr, int tc, int dr, int
dc, int size)
{
if (size == 1)
return;
int t = tile++, L型骨牌号
s =
size2; 分割棋盘
覆盖左上角子棋盘
if (dr < tr + s &&
dc < tc + s)
else
{ 此棋盘中无特殊方格
用 t 号L型骨牌覆盖右下角
board[tr + s -
1][tc + s - 1] = t;
特殊方格在此棋盘中
chessBoard(tr, tc, dr, dc, s);
}
}
覆盖其余方格
chessBoard(tr, tc, tr+s-1, tc+s-1, s);
覆盖右上角子棋盘
if (dr < tr + s && dc >= tc + s)
else
{ 此棋盘中无特殊方格
}
覆盖左下角子棋盘
if (dr >= tr + s && dc <
tc + s)
else
{ 用 t 号L型骨牌覆盖右上角
}
覆盖右下角子棋盘
if (dr >=
tr + s && dc >= tc + s)
else
{ 用
t 号L型骨牌覆盖左上角
}
board[tr +
s][tc + s] = t;
覆盖其余方格
chessBoard(tr+s,
tc+s, tr+s, tc+s, s);
特殊方格在此棋盘中
chessBoard(tr+s, tc+s, dr, dc, s);
board[tr + s][tc + s - 1] = t;
覆盖其余方格
chessBoard(tr+s, tc, tr+s, tc+s-1, s);
特殊方格在此棋盘中
chessBoard(tr+s, tc, dr, dc, s);
用 t 号L型骨牌覆盖左下角
board[tr + s - 1][tc + s]
= t;
覆盖其余方格
chessBoard(tr, tc+s, tr+s-1,
tc+s, s);
特殊方格在此棋盘中
chessBoard(tr, tc+s,
dr, dc, s);
int main()
{
void chessBoard(int tr,
int tc, int dr, int dc, int size);声明函数
int tx=
0,ty=0,dx,dy,zsize=1,k;定义棋盘的左上角方格、特殊方格的行号和列号以及棋盘大小
cout<<请输入特殊方格的行号、列号以及棋盘的大小(K值)n其实用户输入
cin>>dx>>dy>>k;
*********动态的创建二维数组**********
for(int
i=1;i<=k;++i) zsize=zsize*2;
board=new int
*[zsize];
}
for(int i=0;i
}
*********动态创建数组结束************
board[dx][dy]=0;特殊方格用0填充
chessBoard(tx,ty,dx,dy,zsize);
输出结果
for(int j=0;j
}
for(int m=0;m
}
cout<
system(
free(board);
board = NULL;
return 0;
四．实验截图：
五．心得体会：
通过这次实践，我对分治法的理解程度又加深了很多。实现过程中碰到很多细小而繁<
br>杂的问题，这让我意识到课本上的知识终究是课本上的，要变成自己的，必须经过亲身实践。
写代
码是枯燥的，但是看到自己成果的那一刻又是喜悦的。残缺棋盘问题是一个二维问题的
二分法分解，这种
算法思想在以后的编程生涯中必定会用到很多。经过这次实践，我了解到
了分治的实际应用情况，以后碰
到这种问题就不会毫无头绪。总之，我学到了很多。