分治法——棋盘问题

题意：给你一个正方形棋盘，尺寸是 2 的次方，2*2、4*4 、8*8 …… 棋盘上有一个缺点。要求：用 L 形的骨牌覆盖整个棋盘，不能覆盖到缺点。

先上代码。

#include<iostream>
using namespace std;

int tie = 1;
int map[1005][1005];

void ChessBoard(int tr, int tc, int size, int dr, int dc)
{
	if(size == 1) return;
	int t = tie++;
	int s = size/2;
/*处理左上角*/
	if(dr < tr + s && dc < tc + s)
		ChessBoard(tr,tc,s,dr,dc);
	else{
		map[tr+s-1][tc+s-1] = t;
		ChessBoard(tr,tc,s,tr+s-1,tc+s-1);
	}
/*处理右上角*/
	if(dr < tr + s && dc >= tc + s)
		ChessBoard(tr,tc+s,s,dr,dc);
	else{
		map[tr+s-1][tc+s] = t;
		ChessBoard(tr,tc+s,s,tr+s-1,tc+s);
	}
/*处理左下角*/
	if(dr >= tr + s && dc < tc + s)
		ChessBoard(tr+s,tc,s,dr,dc);
	else{
		map[tr+s][tc+s-1] = t;
		ChessBoard(tr+s,tc,s,tr+s,tc+s-1);
	}
/*处理右下角*/
	if(dr >= tr + s && dc >= tc + s)
		ChessBoard(tr+s,tc+s,s,dr,dc);
	else{
		map[tr+s][tc+s] = t;
		ChessBoard(tr+s,tc+s,s,tr+s,tc+s);
	}
}

int main()
{
	int n;
	cout<<"输入棋盘的尺寸：";
	cin>>n;
	int x,y;
	cout<<"输入缺点的位置：";
	cin>>x>>y;
	map[x][y] = 0;
	ChessBoard(0,0,n,x,y);
	cout<<"棋盘："<<endl;
	for(int i = 0; i < n; i++)
	{ 
		for(int j = 0; j < n; j++)
			printf("%2d ",map[i][j]);
		cout<<"
";
	} 
}

8*8的棋盘如下，缺点为（0，0）：

每次分割的时候，骨牌所在位置是没有缺点的另外三个象限。

　　　　　　　 　 第一次分割

  　　　　　　第二次分割

　　　　　　　 第三次分割　　

　　　　　　　　　　　　图5

　　　　　　　　　　　　 图6

第三次分割完以后，继续填第二次分割的棋盘。见图 5。

第二次分割完以后，继续填第一次分割的棋盘。见图 6。

PS:理解过程以后，编码并不难。注意编码细节，在赋值骨牌号码和使用递归的时候，可以画图模拟过程。确定各参数。