棋盤覆寫問題的算法實作

 在一個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");

 本文轉自 androidguy 51CTO部落格，原文連結：http://blog.51cto.com/androidguy/215381，如需轉載請自行聯系原作者