本文為原創，如需轉載，請注明作者和出處，謝謝！
在一個2^k * 2^k個方格組成的棋盤中，有一個方格與其它的不同，若使用以下四種L型骨牌覆蓋除這個特殊方格的其它方格，如何覆蓋。
四各L型骨牌如下圖1
圖1
棋盤中的特殊方格如圖2
圖2
實現的基本原理是將2^k * 2^k的棋盤分成四塊2^(k - 1) * 2^(k -
1)的子棋盤，特殊方格一定在其中的一個子棋盤中，如果特殊方格在某一個子棋盤中，繼續遞歸處理這個子棋盤，直到這個子棋盤中只有一個方格為止如果特殊方
格不在某一個子棋盤中，將這個子棋盤中的相應的位置設為骨牌號，將這個無特殊方格的了棋盤轉換為有特殊方格的子棋盤，然后再遞歸處理這個子棋盤。以上原理
如圖3所示。
圖3
將棋盤保存在一個二維數組中。骨牌號從1開始，特殊方格為0，如果是一個4 * 4的棋盤，特殊方格為(2,2)，那么程序的輸出為
2 2 3 3
2 1 1 3
4 1 0 5
4 4 5 5
相同數字的為同一骨牌。
下面是棋盤覆蓋問題的c語言實現。
#include <stdio.h>
#define BOARD_SIZE 4
int board[BOARD_SIZE][BOARD_SIZE];
// c1, r1: 棋盤左上角的行號和列號
// c2, r2: 特殊方格的行號和列號
// size = 2 ^ k
void chessboard(int r1, int c1, int r2, int c2, int size)
{
if(1 == size) return;
int half_size;
static int domino_num = 1;
int d = domino_num++;
half_size = size / 2;
if(r2 < r1 + half_size && c2 < c1 + half_size) //特殊方格在左上角子棋盤
{
chessboard(r1, c1, r2, c2, half_size);
}
else // 不在此棋盤，將此棋盤右下角設為相應的骨牌號
{
board[r1 + half_size - 1][c1 + half_size - 1] = d;
chessboard(r1, c1, r1 + half_size - 1, c1 + half_size - 1, half_size);
}
if(r2 < r1 + half_size && c2 >= c1 + half_size) //特殊方格在右上角子棋盤
{
chessboard(r1, c1 + half_size, r2, c2, half_size);
}
else // 不在此棋盤，將此棋盤左下角設為相應的骨牌號
{
board[r1 + half_size - 1][c1 + half_size] = d;
chessboard(r1, c1 + half_size, r1 + half_size - 1, c1 + half_size, half_size);
}
if(r2 >= r1 + half_size && c2 < c1 + half_size) //特殊方格在左下角子棋盤
{
chessboard(r1 + half_size, c1, r2, c2, half_size);
}
else // 不在此棋盤，將此棋盤右上角設為相應的骨牌號
{
board[r1 + half_size][c1 + half_size - 1] = d;
chessboard(r1 + half_size, c1, r1 + half_size, c1 + half_size - 1, half_size);
}
if(r2 >= r1 + half_size && c2 >= c1 + half_size) //特殊方格在左上角子棋盤
{
chessboard(r1 + half_size, c1 + half_size, r2, c2, half_size);
}
else // 不在此棋盤，將此棋盤左上角設為相應的骨牌號
{
board[r1 + half_size][c1 + half_size] = d;
chessboard(r1 + half_size, c1 + half_size, r1 + half_size, c1 + half_size, half_size);
}
}
int main()
{
int i, j;
board[2][2] = 0;
chessboard(0, 0, 2, 2, BOARD_SIZE);
for(i = 0; i < BOARD_SIZE; i++)
{
for(j = 0; j < BOARD_SIZE; j++)
{
printf("%-4d", board[i][j]);
}
printf("\n");
}
}
新浪微博：http://t.sina.com.cn/androidguy 昵稱：李寧_Lining