程序填空题：棋盘覆盖问题（分治法）

用分治法求解棋盘覆盖问题。有一个$$2^{k}$$×$$2^{k}$$（k>0）的棋盘，恰好有一个方格与其他方格不同，称之为特殊方格。现在要用如下的L型骨牌覆盖除了特殊方格外的其他全部方格，骨牌可以任意旋转，并且任何两个骨牌不能重叠。请给出一种覆盖方法。



```c++
#include
#include
#include
#define MAX 1025
using namespace std;
int board[MAX][MAX];
int tile=1;

void ChessBoard(int tr,int tc,int dr,int dc,int size)
{ if(@@[size==1](2)) return; //递归出口
int t=tile++; //取一个L型骨，其牌号为tile
int s=size/2; //分割棋盘
//考虑左上角象限
if(@@[dr @@[ChessBoard(tr,tc,dr,dc,s)](2);
else //此象限中无特殊方格
{ @@[board[tr+s-1][tc+s-1]=t](2); //用t号L型骨牌覆盖右下角
@@[ChessBoard(tr,tc,tr+s-1,tc+s-1,s)](2); //将右下角作为特殊方格继续处理该象限
}
//考虑右上角象限
if(@@[dr=tc+s](2))
@@[ChessBoard(tr,tc+s,dr,dc,s)](2); //特殊方格在此象限中
else //此象限中无特殊方格
{ @@[board[tr+s-1][tc+s]=t](2); //用t号L型骨牌覆盖左下角
@@[ChessBoard(tr,tc+s,tr+s-1,tc+s,s)](2); //将左下角作为特殊方格继续处理该象限
}
//处理左下角象限
if(@@[dr>=tr+s && dc @@[ChessBoard(tr+s,tc,dr,dc,s)](2);
else //此象限中无特殊方格
{ @@[board[tr+s][tc+s-1]=t](2); //用t号L型骨牌覆盖右上角
@@[ChessBoard(tr+s,tc,tr+s,tc+s-1,s)](2); //将右上角作为特殊方格继续处理该象限
}
//处理右下角象限
if(@@[dr>=tr+s && dc>=tc+s](2)) //特殊方格在此象限中
@@[ChessBoard(tr+s,tc+s,dr,dc,s)](2);
else //此象限中无特殊方格
{ @@[board[tr+s][tc+s]=t](2); //用t号L型骨牌覆盖左上角
@@[ChessBoard(tr+s,tc+s,tr+s,tc+s,s)](2); //将左上角作为特殊方格继续处理该象限
}
}

int main()
{
int dr,dc,size;
int j,i;
cin>>size;
cin>>dr>>dc;
ChessBoard(0,0,dr,dc,size);
for(i=0;i cout< for(j=0;j {
cout< }
cout<}
return 0;
}
```
### 输入样例：
第一行输入一个数n表示棋盘大小，第二行输入特殊方格的行列下标。
```in
8
1 2
```

### 输出样例：
输出棋盘。
```out
3 3 4 4 8 8 9 9
3 2 0 4 8 7 7 9
5 2 2 6 10 10 7 11
5 5 6 6 1 10 11 11
13 13 14 1 1 18 19 19
13 12 14 14 18 18 17 19
15 12 12 16 20 17 17 21
15 15 16 16 20 20 21 21
```







答案：
第1空：size==1

第2空：dr
第3空：ChessBoard(tr,tc,dr,dc,s)

第4空：board[tr+s-1][tc+s-1]=t

第5空：ChessBoard(tr,tc,tr+s-1,tc+s-1,s)

第6空：dr=tc+s

第7空：ChessBoard(tr,tc+s,dr,dc,s)

第8空：board[tr+s-1][tc+s]=t

第9空：ChessBoard(tr,tc+s,tr+s-1,tc+s,s)

第10空：dr>=tr+s && dc
第11空：ChessBoard(tr+s,tc,dr,dc,s)

第12空：board[tr+s][tc+s-1]=t

第13空：ChessBoard(tr+s,tc,tr+s,tc+s-1,s)

第14空：dr>=tr+s && dc>=tc+s

第15空：ChessBoard(tr+s,tc+s,dr,dc,s)

第16空：board[tr+s][tc+s]=t

第17空：ChessBoard(tr+s,tc+s,tr+s,tc+s,s)