題目： 在一個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;
}
運行截圖：
