首页 > 专题系列 > 经典问题 > 分治算法之棋盘覆盖问题(完整代码实现)
2014
01-06

分治算法之棋盘覆盖问题(完整代码实现)

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

我在这里是用了一个简化的方式,只是代码简化,还是分治递归思想。一分为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      : coder
// Version     :
// Copyright   : www.acmerblog.com
// 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;}}


  1. Gucci New Fall Arrivals

    This is really nice to know. I hope it will be successful in the future. Good job on this and keep up the good work.