分治算法之棋盘覆盖问题（CPP实现）

这是算法书上关于分治的常见题目，这里给出我的代码实现。

我在这里是用了一个简化的方式，只是代码简化，还是分治递归思想。一分为4，直至2*2时可直接解决。

四种骨牌的摆放刚好对应：dir[4][2] = { { 0, 0 }, { 0, 1 }, { 1, 1 }, { 1, 0 } }; 这四个方向。

而这4个方向，又可用来判断残缺位置的 4个方向（左上，右上，右下，左下）。

因此可以用循环，而不是依次判断四个方向，简化代码。

也可以用一个全局变量title 表示第几个骨牌，然后输出的时候可以用一个title代替ABCD.

【解题思路】：将2^k x 2^k的棋盘，先分成相等的四块子棋盘，其中特殊方格位于四个中的一个，构造剩下没特殊方格三个子棋盘，将他们中的也假一个方格设为特殊方格。如果是：

左上的子棋盘（若不存在特殊方格）—-则将该子棋盘右下角的那个方格假设为特殊方格
右上的子棋盘（若不存在特殊方格）—-则将该子棋盘左下角的那个方格假设为特殊方格
左下的子棋盘（若不存在特殊方格）—-则将该子棋盘右上角的那个方格假设为特殊方格
右下的子棋盘（若不存在特殊方格）—-则将该子棋盘左上角的那个方格假设为特殊方格

当然上面四种，只可能且必定只有三个成立，那三个假设的特殊方格刚好构成一个L型骨架，我们可以给它们作上相同的标记。这样四个子棋盘就分别都和原来的大棋盘类似，我们就可以用递归算法解决。

//============================================================================
// Name        : 棋盘覆盖.cpp
// Author      : 从此醉
// Version     :
// Copyright   : 
// 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

 

参考：http://www.acmerblog.com/divid-conquer-chess-board-3427.html