我在这里是用了一个简化的方式,只是代码简化,还是分治递归思想。一分为4,直至2*2时可直接解决。
四种骨牌的摆放刚好对应:dir[4][2] = { { 0, 0 }, { 0, 1 }, { 1, 1 }, { 1, 0 } }; 这四个方向。
而这4个方向,又可用来判断残缺位置的 4个方向(左上,右上,右下,左下)。
因此可以用循环,而不是依次判断四个方向,简化代码。
也可以用一个全局变量title 表示第几个骨牌,然后输出的时候可以用一个title代替ABCD.
copy:
【解题思路】:将2^k x 2^k的棋盘,先分成相等的四块子棋盘,其中特殊方格位于四个中的一个,构造剩下没特殊方格三个子棋盘,将他们中的也假一个方格设为特殊方格。如果是:
左上的子棋盘(若不存在特殊方格)----则将该子棋盘右下角的那个方格假设为特殊方格
右上的子棋盘(若不存在特殊方格)----则将该子棋盘左下角的那个方格假设为特殊方格
左下的子棋盘(若不存在特殊方格)----则将该子棋盘右上角的那个方格假设为特殊方格
右下的子棋盘(若不存在特殊方格)----则将该子棋盘左上角的那个方格假设为特殊方格
当然上面四种,只可能且必定只有三个成立,那三个假设的特殊方格刚好构成一个L型骨架,我们可以给它们作上相同的标记。这样四个子棋盘就分别都和原来的大棋盘类似,我们就可以用递归算法解决。
//============================================================================ // Name : 棋盘覆盖.cpp // Author : gaotong // Version : // Copyright : Your copyright notice // Description : A,B,C,D分别表示四种类型的骨牌.即 // A B CC DD // AA BB C D //============================================================================
#include <iostream> using namespace std; int N, X, Y; //棋盘大小, 残缺位置 X,Y char map[1000][1000]; //棋盘数组 int dir[4][2] = { { 0, 0 }, { 0, 1 }, { 1, 1 }, { 1, 0 } }; //四种L棋的放置 char pieces[4] = { 'A', 'B', 'C', 'D' }; //4种表示 int title = 0; //style 表示那种类型的骨牌; r,t表示放置骨牌的区域(2*2)的左上角位置 void set_piece(int style, int r, int c) { title++; for (int i = 0; i < 4; i++) if (i == style) { //每种style 对用dir中的摆放方式 for (int j = 0; j < 4; j++) if (i != j) map[r + dir[j][0]][c + dir[j][1]] = pieces[i]; } } //startR,starC(行,列)区域的左上角位置; dr,dc(行,列)残缺位置; 区域大小 void chessBoard(int startR, int startC, int dr, int dc, int size) { if (size == 1) return; int s = size / 2; int rr = dr >= startR + s; //rr 为1 表示在右方 int cc = dc >= startC + s; //cc 为1表示在下方 for (int i = 0; i < 4; i++) { if (dir[i][0] == rr && dir[i][1] == cc) { //根据残缺的位置,在区域中间放置一个骨牌. //例:如果是 rr=0 cc=0 即残缺位置在左上方,对应 dir[0] = {0,0} //即style=0, 第一种骨牌 set_piece(i, startR + s - 1, startC + s - 1); for (int j = 0; j < 4; j++) { if (j == i) //摆放有残缺位置的 1/4 chessBoard(startR + s * dir[j][0], startC + s * dir[j][1], dr, dc, s); else { //分别摆放余下的3/4. 残缺位置即在区域中央放置的骨牌 在当前区域的位置 (例:对于右上角区域,残缺位置在坐下角位置) chessBoard(startR + s * dir[j][0], startC + s * dir[j][1], startR + s - 1 + dir[j][0], startC + s - 1 + dir[j][1], s); } } } } } int main() { cout << "欢迎使用棋盘覆盖程序:" << endl; cout << "分别A,B,C,D代表4种不同方向的骨牌:" << endl << endl; cout << " A B CC DD" << endl; cout << " AA BB C D" << endl << endl; cout << "输入3个数,分别为棋盘大小N(小于1000),残缺位置X,Y(1到N之间):" << endl; cin >> N >> X >> Y; //判断N是否为2的n次方 if ((N & (N - 1)) || X > N || X < 1 || Y < 1 || Y > N) { cout << "输入不合法" << endl; } else { chessBoard(0, 0, X - 1, Y - 1, N); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cout << map[i][j]; } cout << endl; } } return 0; }
输出:
欢迎使用棋盘覆盖程序: 分别A,B,C,D代表4种不同方向的骨牌: A B CC DD AA BB C D 输入3个数,分别为棋盘大小N(小于1000),残缺位置X,Y(1到N之间): 4 2 3 CCDD CB D BBBA BBAA
这是书上的代码(不全):
void ChessBoard(int tr, int tc, int dr,int dc, int size)
{ if (size==1) return;
int t=tile++,// L型骨牌数
s=size/2; // 分割棋盘
//覆盖左上角子棋盘
if (dr< tr +s && 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-l,s);}
//覆盖右上角子棋盘
if (dr <= tr +s && dc >= tc+S)
//特殊方格在此棋盘中
ChessBoard(tr,tc+s ,dr,dc,S);
else{//此棋盘中无特殊方格
//用t号骨牌覆盖左下角
Board[tr+s-1][tc+s]=t;
//覆盖其余方格
Chessboard(tr,tc+s,tr+s-1,tc+s,s);}
………………...
void outputBoard( int size)
{ for inti=0;i<size;i++){
for intj=0 ;j<size ;j++);
cout<<setw(5)<<board [i][j];
cout<<endl;}}