算法设计与分析----棋盘覆盖

在一个2^k × 2^k （k≥0）个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为特殊方格。显然，特殊方格在棋盘中可能出现的位置有4^k 种，因而有 4^k种不同的棋盘，图4.10(a)所示是k=2时16种棋盘中的一个。棋盘覆盖问题（chess cover problem）要求用图4.10(b)所示的4种不同形状的L型骨牌覆盖给定棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。

棋盘覆盖问题采用分治策略求解，将棋盘递归的向下划分，如4x4的棋盘首先划分为4个2x2的棋盘，再将每个2x2的棋盘划分为4个1x1的棋盘。分治的基本思想是划分为同样的子问题求解，但是这要怎么划分呢，特殊的点只有一个，如果这样划分不就不一样了吗？不一样就要变成一样，当我们划分为4个4x4时，
只有左上有特殊点，而其余三个都没有，这时我们就要构造特殊点，用一个L型骨牌覆盖：

这样我们把红色的棋盘也当成特殊点，再进行递归就可以了。

#include<bits/stdc++.h>
using namespace std;
int mp[50][50];
int cnt = 0;
//zx，zy为当前棋盘的左上角坐标，spx，spy为特殊点的坐标。
void dfs(int zx,int zy,int spx,int spy,int size)
{
	if(size == 1)//如果划分到只剩1个棋盘了，就直接退出
		return ;
	int t = ++cnt;//骨牌号
	int s = size/2;//下一次递归的棋盘大小
	//printf("1");
	// 如果特殊点在划分棋盘后的左上部分
	if(zx+s > spx && zy+s > spy) //left top
	{
		//直接划分，不用覆盖
		dfs(zx,zy,spx,spy,s);
	}
	else 
	{
		//否则就在左上部分的右下角覆盖，继而将覆盖的点当作特殊点，继续划分
		//（配合上面的图理解）
		mp[zx+s-1][zy+s-1]=t;
		dfs(zx,zy,zx+s-1,zy+s-1,s);
	}
	// 如果特殊点在划分棋盘后的右上部分
	if(zx+s > spx && zy+s <= spy) //right top
	{
		//直接划分，不用覆盖
		dfs(zx,zy+s,spx,spy,s);
	}
	else
	{
		//否则就在右上部分的左下角覆盖，继而将覆盖的点当作特殊点，继续划分
		mp[zx+s-1][zy+s]=t;
		dfs(zx,zy+s,zx+s-1,zy+s,s);
	}
	// 如果特殊点在划分棋盘后的左下部分
	if(zx+s <= spx && zy+s >spy) //left bottom
	{
		//直接划分，不用覆盖
		dfs(zx+s,zy,spx,spy,s);
	}
	else
	{
		//否则就在左下部分的右上角覆盖，继而将覆盖的点当作特殊点，继续划分
		mp[zx+s][zy+s-1]=t;
		dfs(zx+s,zy,zx+s,zy+s-1,s);
	}
	// 如果特殊点在划分棋盘后的右下部分
	if(zx+s <= spx && zy+s <= spy) //right bottom
	{
		//直接划分，不用覆盖
		dfs(zx+s,zy+s,spx,spy,s);
	}
	else
	{
		//否则就在右下部分的左上角覆盖，继而将覆盖的点当作特殊点，继续划分
		mp[zx+s][zy+s]=t;
		dfs(zx+s,zy+s,zx+s,zy+s,s);
	}	
}
int main()
{
	int n;
	int spx,spy;
	scanf("%d",&n); //输入棋盘的大小
	int size = n;
	scanf("%d%d",&spx,&spy); //输入特殊点的位置
	dfs(0,0,spx,spy,size); //棋盘覆盖
	for(int i = 0;i<n;i++)
	{
		for(int j = 0;j<n;j++)
		{
			printf("%5d ",mp[i][j]);
		}
		printf("\n\n");
	}
}