雖然這個(gè)問題已經(jīng)在網(wǎng)上被討論遍了，但是最近從新拾起算法，感覺有必要夯實(shí)一下基礎(chǔ)。

棋盤覆蓋問題：
首先大致描述一下題目：
在一個(gè)2^k×2^k個(gè)方格組成的棋盤中,若有一個(gè)方格與其他方格不同,則稱該方格為一特殊方格,且稱該棋盤為一個(gè)特殊棋盤.顯然特殊方格在棋盤上出現(xiàn)的位置有4^k種情形.因而對任何
k≥0,有4^k種不同的特殊棋盤.
下圖–圖(1)中的特殊棋盤是當(dāng)k=2時(shí)16個(gè)特殊棋盤中的一個(gè)：

 

圖(1)

題目要求在棋盤覆蓋問題中,要用下圖—圖(2)所示的4種不同形態(tài)的L型骨牌覆蓋一個(gè)給定的特殊棋盤上除特殊方格以外的所有方格,且任何2個(gè)L型骨牌不得重疊覆蓋.

 

圖(2)

思路分析：
當(dāng)k>0時(shí),將2^k×2^k棋盤分割為4個(gè)2^k－1×2^k－1子棋盤,如下圖–圖(3)所示：

 

圖(3)

特殊方格必位于4個(gè)較小子棋盤之一中,其余3個(gè)子棋盤中無特殊方格.為了將這3個(gè)無特殊方格的子棋盤轉(zhuǎn)化為特殊棋盤,可以用一個(gè)L型骨牌覆蓋這3個(gè)較小棋盤的會(huì)合處。
如下圖–圖(4)所示,這3個(gè)子棋盤上被L型骨牌覆蓋的方格就成為該棋盤上的特殊方格,從而原問題轉(zhuǎn)化為4個(gè)較小規(guī)模的棋盤覆蓋問題.遞歸地使用這種分割,直至棋盤簡化為1×1棋盤。

以下是代碼：

 

/*
Author: Tanky Woo
Blog:   www.WuTianQi.com
棋盤覆蓋問題
分治法
2010-12-3
*/
#include <iostream>
using namespace std;
const int N = 11;
int Board[N][N];
int tile = 0;
 
/*
tr:棋盤左上角方格的行號
tc:棋盤左上角方格的列號
dr:特殊方格所在的行號
dc:特殊方格所在的列號
size:方形棋盤的邊長
*/
void ChessBoard(int tr, int tc, int dr, int dc, int size)
{
    if(size == 1)
        return;
    int t = ++tile, s = size/2;
 
    //覆蓋左上角子棋盤
    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
    {
        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);
    }
}
 
void DisplayBoard(int size)
{
    for(int i=1; i<=size; ++i)
    {
        for(int j=1; j<=size; ++j)
            printf("%2d ", Board[i][j]);
        printf("\n");
    }
}
 
int main()
{
    ChessBoard(1, 1, 1, 2, 4);
    DisplayBoard(4);
    return 0;
}