分治算法-棋盘覆盖问题

在一个2k×2k个方格组成的棋盘中，恰有一个方格与其它方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。

#include<stdio.h>
#define MAX 1025

//问题表示
int k;				//棋盘大小
int x,y;			//特殊方格的位置

//求解问题表示
int board[MAX][MAX];
int tile=1;		

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