棋盘覆盖

题目大意：
在一个2k×2k 个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。
在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。
易知，在任何一个2k×2k的棋盘覆盖中，用到的L型骨牌个数恰为(4k-1)/3。
分析：
当k>0时，将2k×2k棋盘分割为4个2k-1×2k-1 子棋盘(a)所示。
特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如 (b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘1×1。

变量含义说明：
特殊方格位置（dr,dc）
if棋盘大小size==1,就结束
else 划分成4个较小规模的子问题，用L型骨牌（编号相同）覆盖其余三个不含特殊方格的区域的交合处，使其成为残缺棋盘。

#include <bits/stdc++.h>
using namespace std;
#define m 8
#define n 8
int tile=0;//全局变量，L型骨牌编号 
int Board[m][n]={0};//记录覆盖情况 
 
void ChessBoard(int tr,int tc,int dr,int dc,int size){
	int s;
	if(size==1) return;
	else s=size/2;//size=2^k,s=2^(k-1),s相当于边长
	int t=++tile;//设置L骨牌编号 
	if((dr<tr+s)&&(dc<tc+s))//特殊方格在左上角区域内 
		ChessBoard(tr,tc,dr,dc,s);//对这个区域继续覆盖 
	else {
		//安装特殊方格，L型骨牌覆盖
		Board[tr+s-1][tc+s-1]=t;
		ChessBoard(tr,tc,tr+s-1,tc+s-1,s);
	} 
	if((dr<tr+s)&&(dc>=tc+s))//特殊方格在右上角区域内 
		ChessBoard(tr,tc+s,dr,dc,s);
	else {
		Board[tr+s-1][tc+s]=t;
		ChessBoard(tr,tc+s,tr+s-1,tc+s,s);
	} 
	if((dr>=tr+s)&&(dc<tc+s))//特殊方格在左下角区域内 
		ChessBoard(tr+s,tc,dr,dc,s);
	else {
		Board[tr+s][tc+s-1]=t;
		ChessBoard(tr+s,tc,tr+s,tc+s-1,s);
	}
	if((dr>=tr+s)&&(dc>=tc+s))//特殊方格在右下角区域内 
		ChessBoard(tr+s,tc+s,dr,dc,s);
	else {
		Board[tr+s][tc+s]=t;
		ChessBoard(tr+s,tc+s,tr+s,tc+s,s);
	}
}

int main(){
	cout<<"棋盘最初面貌："<<endl;
	for(int i=0;i<m;i++){
		for(int j=0;j<n;j++){
			cout<<Board[i][j]<<'\t';
		}
		cout<<endl;
	} 
	cout<<endl;
	ChessBoard(0,0,2,5,8);
	cout<<"棋盘覆盖完成后的面貌："<<endl;
	for(int i=0;i<m;i++){
		for(int j=0;j<n;j++){
			cout<<Board[i][j]<<'\t';
		}
		cout<<endl;
	} 
	return 0; 
}