棋盤覆蓋（分治法）

題目： 在一個2^k x 2^k 個方格組成的棋盤中，若恰有一個方格與其他方格不同，則稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。現在要用4種不同形態的L型骨牌覆蓋一個給定的特殊棋盤上除特殊方格以外的所有方格，且任意2個L型骨牌不得重疊覆蓋。  解釋一下什麼是L型骨牌：就是由三個方格組成的一個角，可知有四種；

思路：將一個棋盤均分成四個小的棋盤，沿各邊的中點切分，特殊方格必定位於4個較小的棋盤之一中，其餘的3個子棋盤中無特殊方格。為了將這3個無特殊子棋盤的子棋盤轉化為特殊棋盤，我們可以用一個L型骨牌覆蓋這3個較小棋盤的會合出，遞歸下去，當棋盤邊長為1時終止；

代碼如下：

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <set>
#include <queue>
#include <vector>
using namespace std;
int tot;
int board[105][105];
void chessboard(int tr,int tc,int dr,int dc,int size)
{
    if(size==1) return ;
    int t=tot++;
    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;
        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()
{
    int dr,dc,s;
    printf("輸入格式為： 特殊方格橫坐標、縱坐標  棋盤邊長\n");
    while(scanf("%d%d%d",&dr,&dc,&s)!=EOF)
    {
        tot=1;
        memset(board,0,sizeof(board));
        chessboard(0,0,dr,dc,s);
        for(int i=0;i<s;i++)
        {
            for(int j=0;j<s;j++)
                printf("%-2d ",board[i][j]);
            cout<<endl;
        }
    }
    return 0;
}

運行截圖：