网站漂浮图片代码,商业网站服务,深圳工程建设交易服务中心网站,金融中介做网站需要问题描述 棋盘覆盖问题要求在2^k * 2^k 个方格组成的棋盘中#xff0c;你给定任意一个特殊点#xff0c;用一种方案实现对除该特殊点的棋盘实现全覆盖。
建立模型如图#xff1a;
解决方案就是利用分治法#xff0c;将方形棋盘分成4部分#xff0c;如果该特殊点在某一部…问题描述 棋盘覆盖问题要求在2^k * 2^k 个方格组成的棋盘中你给定任意一个特殊点用一种方案实现对除该特殊点的棋盘实现全覆盖。
建立模型如图
解决方案就是利用分治法将方形棋盘分成4部分如果该特殊点在某一部分我们就去递归他如果不在某一部分我们假设一个点为特殊点同样递归下去知道全覆盖。
左上角的子棋盘若不存在特殊方格则将该子棋盘右下角的那个方格假设为特殊方格
右上角的子棋盘若不存在特殊方格则将该子棋盘左下角的那个方格假设为特殊方格
左下角的子棋盘若不存在特殊方格则将该子棋盘右上角的那个方格假设为特殊方格
右下角的子棋盘若不存在特殊方格则将该子棋盘左上角的那个方格假设为特殊方格
在一个2^k * 2^k个方格组成的棋盘中有一个方格与其它的不同若使用以下四种L型骨牌覆盖除这个特殊方格的其它方格如何覆盖。四个L型骨牌如下图 实现的基本原理是将2^k * 2k的棋盘分成四块2(k - 1) * 2^(k - 1)的子棋盘特殊方格一定在其中的一个子棋盘中如果特殊方格在某一个子棋盘中继续递归处理这个子棋盘直到这个子棋盘中只有一个方格为止如果特殊方格不在某一个子棋盘中将这个子棋盘中的相应的位置设为骨牌号将这个无特殊方格的了棋盘转换为有特殊方格的子棋盘然后再递归处理这个子棋盘。以上原理如图所示 #includeiostream
#includebits/stdc.h
using namespace std;
int tile 1;
int Borad[100][100];
/*** tr : 棋盘左上角的行号tc棋盘左上角的列号* dr : 特殊方格左上角的行号dc特殊方格左上角的列号* size size 2^k 棋盘规格为2^k*2^k*/
void ChessBoard(int tr,int tc,int dr,int dc,int size)
{if(size1)return;int t tile;int s size / 2;if( dr trs dc tcs )//特殊方格在棋盘的左上角{ChessBoard(tr, tc, dr, dc, s);}else//特殊方格不在棋盘的左上角时{Borad[tr s-1][tc s-1] t;ChessBoard(tr, tc, tr s - 1, tc s - 1, s);}if( dr trs tcs dc )//特殊方格在棋盘的右上角{ChessBoard(tr, tc s, dr, dc, s);}else//特殊方格不在棋盘的右上角{Borad[tr s-1][tc s]t;ChessBoard(tr, tc s, tr s-1, tc s , s);}if( trs dr dc tcs )//特殊方格在棋盘的左下角{ChessBoard(tr s, tc, dr, dc, s);}else//特殊方格不在棋盘的左下角{Borad[trs][tcs-1]t;ChessBoard(tr s, tc, trs, tcs-1, s);}if( trs dr tcs dc )//特殊方格在棋盘的右下角{ChessBoard(tr s, tc s, dr, dc, s);}else//特殊方格不在棋盘的右下角{Borad[tr s][tc s]t;ChessBoard(tr s, tc s, trs, tcs, s);}}
int main()
{cout 输入K的值;int k;cin k;int temp 1;for (int i 0; i k;i){temp temp * 2;}int size temp;int x, y;//存储特殊点所在的行列cout 输入特殊点在的行,列(表示特殊点的值为-1);cin x y;Borad[x][y] -1;ChessBoard(0, 0, x, y, size);for (int i 0; i size;i){for (int j 0; j size;j){cout setw(4) Borad[i][j] ;}cout endl;}system(pause);}上述算法中 使用了一个二维数组Board[][]表示棋盘Board[0][0]是棋盘左上角的方格tile是算法中的一个全局变量用来表示L型骨牌其初始值为0。 tr:棋盘左上角方格的行号 tc:棋盘左上角方格的列号 dr:特殊方格的行号 dc:特殊方格的列号 size:size2^k 棋盘的规格2^K* 2^K
标记的次序
