棋盤覆蓋問題 （分治）

問題描敘：

在一個2k×2k 個方格組成的棋盤中，恰有一個方格與其它方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。

在棋盤覆蓋問題中，要用圖示的4種不同形態的L型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，

且任何2個L型骨牌不得重疊覆蓋。

分析：

當k>0時，將2k×2k棋盤分割為4個2k-1×2k-1 子棋盤(a)所示。
特殊方格必位於4個較小子棋盤之一中，其余3個子棋盤中無特殊方格。為了將這3個無特殊方格的子棋盤轉化為特殊棋盤，

可以用一個L型骨牌覆蓋這3個較小棋盤的會合處，如 (b)所示，從而將原問題轉化為4個較小規模的棋盤覆蓋問題。

遞歸地使用這種分割，直至棋盤簡化為棋盤1×1。

實例：

    將棋盤保存在一個二維數組中。骨牌號從1開始，特殊方格為0，如果是一個4 * 4的棋盤，特殊方格為(2,2)，那麼程序的輸出為

2   2   3   3  
2   1   1   3  
4   1   0   5  
4   4   5   5

相同數字的為同一骨牌。

[cpp]
/*
tr: 棋盤左上角方格的行號；
tc: 棋盤左上角方格的列號；
dr: 特殊方格所在的行號；
dc：特殊方格所在的列號；
size: size = 2^k,棋盤規格為2^k * 2^k;
*/ 
void  chessBoard(int tr, int tc, int dr, int dc, int size) 
{ 
    if(1 == size) return ; 
    int t = tile++, //L型骨牌號  
    s = size>>1; //分割棋盤  
 
    //覆蓋左上角子棋盤  
    if(dr <tr + s && dc < tc + s) 
        //特殊方格在此棋盤中  
        chessBoard(tr, tc, dr, dc, s); 
    else  
    { 
        //用t號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 //此棋盤中無特殊方格  
    { 
        //用t號L型骨牌覆蓋左下角  
        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 //用t號L型骨牌覆蓋右上角  
    { 
        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 //用t號L型骨牌覆蓋左上角  
    { 
        board[tr+s][tc+s] = t; 
        //覆蓋其余方格  
        chessBoard(tr+s,tc+s,tr+s,tc+s,s); 
    } 
} 

/*
tr: 棋盤左上角方格的行號；
tc: 棋盤左上角方格的列號；
dr: 特殊方格所在的行號；
dc：特殊方格所在的列號；
size: size = 2^k,棋盤規格為2^k * 2^k;
*/
void  chessBoard(int tr, int tc, int dr, int dc, int size)
{
 if(1 == size) return ;
 int t = tile++, //L型骨牌號
 s = size>>1; //分割棋盤

 //覆蓋左上角子棋盤
 if(dr <tr + s && dc < tc + s)
  //特殊方格在此棋盤中
  chessBoard(tr, tc, dr, dc, s);
 else
 {
  //用t號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 //此棋盤中無特殊方格
 {
  //用t號L型骨牌覆蓋左下角
  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 //用t號L型骨牌覆蓋右上角
 {
  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 //用t號L型骨牌覆蓋左上角
 {
  board[tr+s][tc+s] = t;
  //覆蓋其余方格
  chessBoard(tr+s,tc+s,tr+s,tc+s,s);
 }
}