棋盘覆盖
一、什么是棋盘覆盖
在一个2kⅹ2k个方格组成的棋盘中,若恰有一个方格与其他方格不同,则称该方格为特殊方格,且称该棋盘为一特殊棋盘。
显然,特殊方格出现的位置有4k 种情况,即k>=0,有4k 种不同的特殊棋盘
棋盘覆盖:用4种不同的L型骨牌覆盖一个给定的特殊棋盘(即特殊方格的位置已经确定了)上除去特殊方格外的所有方格,且任何两个L型骨牌不得重复覆盖。
按照规则,我们很容易知道,在2kⅹ2k的棋盘覆盖中,用到的L型骨盘数恰为(4k-1)/3,即(所有方格个数-特殊方格个数)/3
如下图,为k=2时的一个特殊棋盘(相同颜色的三个小方格组成一个L型骨牌)和4种不同形态的L型骨牌,蓝色的为特殊方格
二、证明棋盘覆盖有解
数学归纳法
-
当n=1(2ⅹ2棋盘),该问题有解
-
假设当n=k时(2kⅹ2k棋盘),该问题有解
-
那么当n=k+1时(2k+1ⅹ2k+1棋盘),将棋盘划分为4个2kⅹ2k子棋盘,特殊方格位于4个子棋盘之一中,而其他3个子棋盘中无特殊方格。
-
如何将这3个无特殊方格的子棋盘转化为特殊棋盘?
-
用一个L型骨牌覆盖这3个较小棋盘的会合处,将原问题转化为4个n=k时的子问题,因为n=k时有解,所以n=k+1时也有解。
-
三、实现棋盘覆盖的思路和方法
棋盘覆盖实现的基本方法为分治法
分治法的基本思路:将一个规模为n的问题分解为k个规模较小的子问题,这些子问题相互独立且与原问题相同。递归地解决这些子问题,然后将各个子问题的解合并得到原问题的解。简单地说,就是将规模为n的问题自顶向下分解,直到小问题分解到足够小,可以解决时,再自底向上合并,从而得到原来的解。
当k=0时(1ⅹ1棋盘),及特殊方格,骨牌数为0
当k >0时,将2kⅹ2k棋盘分割为4个2k-1ⅹ2k-1子棋盘了,如图
特殊方格位于4个较小子棋盘之一中,而其余3个子棋盘中无特殊方格。
在递归之前要将原问题转化为4个较小规模的相同子问题。(用一个L型骨牌覆盖这3个子棋盘的会合处),如图
从图上可以看出,这三个子棋盘上被L型骨牌覆盖的方格就成为该棋盘上的特殊方格,从而将问题分解为4个较小规模的棋盘覆盖问题。
递归地使用这种分割方法,直至棋盘简化为1ⅹ1棋盘,就结束递归。
四、棋盘覆盖的具体实现代码
代码分析
—-> 对每个子棋盘按照左上,右上,右下,左下的顺时针顺序铺满棋盘。(顺序不一样,铺出来的编号也不一样)
每次都对分割后的四个小方块进行判断,判断特殊方格是否在里面。
-
如果特殊方块在里面,这直接递归下去即可,
-
如果不在,这根据分割的四个方块的不同位置,把右下角、左下角、左上角、右上角的方格标记为特殊方块,然后继续递归。
在递归函数里,还要有一个变量h来记录边的方格数,每次对方块进行划分时,边的方格数都会减半,这个变量是为了方便判断特殊方格的位置。
代码实现
x:棋盘左上角方格的行号
y:棋盘左上角方格的列号
a:特殊方格的行号
b:特殊方格的列号
length:2k,棋盘规模:2kⅹ2k
#include<iostream>
#include<iomanip>
//setw(n)是c++中在输出操作中使用的字段宽度设置,n表示字段宽度。
using namespace std;
int matrix[100][100];
int num = 0;
void chessBoard(int x, int y, int a, int b, int length);
int main()
{
int a, b, length;
cout << "请输入棋盘的行列号";
cin >> length;
cout << "请输入特殊方格的行列号";
cin >> a >> b;
matrix[a][b] = 0;
chessBoard(1, 1, a, b, length);
for (int i = 1; i <= length; i++){
for (int j = 1; j <= length; j++){
cout << setw(4) << matrix[i][j];
}
cout << endl;
}
return 0;
}
void chessBoard(int x, int y, int a, int b, int length) {
//如果棋盘上只有一个方格,且该方格为一特殊方格
if (length == 1){
return;
}
int h = length / 2; //分割棋盘
int t = ++num; //L型骨牌号(从1开始)
/*左上角*/
if (a < x + h && b < y + h){ //特殊方格在此棋盘中则划分
chessBoard(x, y, a, b, h);
}else{ //否则先覆盖右下角的方格(用t号L型骨牌),再划分
matrix[x + h - 1][y + h - 1] = t;
chessBoard(x, y, x + h - 1, y + h- 1, h);
}
/*右上角*/
if (a < x + h && b >= y + h){ //特殊方格在此棋盘中则划分
chessBoard(x, y + h, a, b, h);
}else{ //否则先覆盖左下角的方格(用t号L型骨牌),再划分
matrix[x + h - 1][y + h] = t;
chessBoard(x, y + h, x + h - 1, y + h, h);
}
/*右下角*/
if (a >= x + h && b >= y + h){ //特殊方格在此棋盘中则划分
chessBoard(x + h, y + h, a, b, h);
}else{ //否则先覆盖左上角的方格(用t号L型骨牌),再划分
matrix[x + h][y + h] = t;
chessBoard(x + h, y + h, x + h, y + h, h);
}
/*左下角*/
if (a >= x + h && b < y + h){ //特殊方格在此棋盘中则划分
chessBoard(x + h, y, a, b, h);
}else{ //否则先覆盖右上角的方格(用t号L型骨牌),再划分
matrix[x + h][y + h - 1] = t;
chessBoard(x + h, y, x + h, y + h - 1, h);
}
}
运行结果如下图
参考链接:https://www.cnblogs.com/crx234/p/5988055.html
五、算法分析
设T(k)是如上算法覆盖一个2kⅹ2k期盼所用的时间
由于覆盖一个2kⅹ2k期盼所需的L型骨牌个数为(4k-1)/3
故该算法为渐近意义下的最优算法。
今天的文章棋盘覆盖问题_8乘8棋盘覆盖怎么覆盖「建议收藏」分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/72483.html