一、问题描述
在一个 2k * 2k（k ≥ 0）个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为特殊方格，显然，特殊方格在棋盘中出现的位置有 4k 种情形，因而有 4k 种不同的棋盘。
二、算分分析
用分治策略。
- 当 k > 0 时，将 2k * 2k 棋盘分割成 4 个 2k-1 * 2k-1 子棋盘，特殊方格必定只位于某个子棋盘中。
- 用一个 L 型骨牌覆盖 3 个无特殊方格子棋盘的结合处，由原问题转化成 4 个较小规模的棋盘覆盖子问题。
三、代码实现
#include <stdio.h>
#define max 1024
int board[max][max]; // 最大棋盘
static int tile = 0; // 覆盖标志位
/**
* （tr，tc） 棋盘左上角的方格坐标
* （dr，dc） 特殊方格所在的坐标
* size 是棋盘的行数和列数
*/
void ChessBoard(int tr,int tc,int dr,int dc,int size)
{
if(size == 1) return; // 递归到棋盘大小为 1 时，则结束递归
int t = tile++; // L型骨牌号
int 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;
// 在构造完特殊方格之后，棋盘的左上角的四分之一又有了特殊方格，所以就对左上角棋盘的四分之一进行棋盘覆盖，直到棋盘大小为 1 * 1
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 {
// 用 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);
}
}
int main()
{
int size = 8, dr = 0, dc = 0;
printf("不可覆盖点的值为 -1！
");
board[dr][dc] = -1;
ChessBoard(0, 0, dr, dc, size);
for(int m = 0; m < size; m++)
{
printf("%2d", board[m][0]);
for(int n = 1; n < size; n++) {
printf(" %2d", board[m][n]);
}
printf("
");
}
return 0;
}
不可覆盖点的值为 -1！
-1 2 3 3 7 7 8 8
2 2 1 3 7 6 6 8
4 1 1 5 9 9 6 10
4 4 5 5 0 9 10 10
12 12 13 0 0 17 18 18
12 11 13 13 17 17 16 18
14 11 11 15 19 16 16 20
14 14 15 15 19 19 20 20