問題描述
棋盤覆蓋問題要求在2^k * 2^k 個方格組成的棋盤中，你給定任意一個特殊點，用一種方案實現(xiàn)對除該特殊點的棋盤實現(xiàn)全覆蓋。

建立模型如圖：

解決方案就是利用分治法，將方形棋盤分成4部分，如果該特殊點在某一部分，我們就去遞歸他，如果不在某一部分，我們假設(shè)一個點為特殊點，同樣遞歸下去，知道全覆蓋。

左上角的子棋盤（若不存在特殊方格）：則將該子棋盤右下角的那個方格假設(shè)為特殊方格；

右上角的子棋盤（若不存在特殊方格）：則將該子棋盤左下角的那個方格假設(shè)為特殊方格；

左下角的子棋盤（若不存在特殊方格）：則將該子棋盤右上角的那個方格假設(shè)為特殊方格；

右下角的子棋盤（若不存在特殊方格）：則將該子棋盤左上角的那個方格假設(shè)為特殊方格；

在一個2^k * 2^k個方格組成的棋盤中，有一個方格與其它的不同，若使用以下四種L型骨牌覆蓋除這個特殊方格的其它方格，如何覆蓋。四個L型骨牌如下圖：

實現(xiàn)的基本原理是將2^k * 2^{k的棋盤分成四塊2}(k - 1) * 2^(k - 1)的子棋盤，特殊方格一定在其中的一個子棋盤中，如果特殊方格在某一個子棋盤中，繼續(xù)遞歸處理這個子棋盤，直到這個子棋盤中只有一個方格為止如果特殊方格不在某一個子棋盤中，將這個子棋盤中的相應(yīng)的位置設(shè)為骨牌號，將這個無特殊方格的了棋盤轉(zhuǎn)換為有特殊方格的子棋盤，然后再遞歸處理這個子棋盤。以上原理如圖所示：

#include<iostream> #include<bits/stdc++.h> using namespace std; int tile = 1; int Borad[100][100]; /*** tr : 棋盤左上角的行號，tc棋盤左上角的列號* dr : 特殊方格左上角的行號，dc特殊方格左上角的列號* size ：size = 2^k 棋盤規(guī)格為2^k*2^k*/ void ChessBoard(int tr,int tc,int dr,int dc,int size) {if(size==1)return;int t = tile++;int s = size / 2;if( dr< tr+s && dc< tc+s )//特殊方格在棋盤的左上角{ChessBoard(tr, tc, dr, dc, s);}else//特殊方格不在棋盤的左上角時；{Borad[tr + s-1][tc + s-1] = t;ChessBoard(tr, tc, tr + s - 1, tc + s - 1, s);}if( dr< tr+s && tc+s <=dc )//特殊方格在棋盤的右上角{ChessBoard(tr, tc + s, dr, dc, s);}else//特殊方格不在棋盤的右上角{Borad[tr + s-1][tc + s]=t;ChessBoard(tr, tc + s, tr + s-1, tc + s , s);}if( tr+s<= dr && dc < tc+s )//特殊方格在棋盤的左下角{ChessBoard(tr + s, tc, dr, dc, s);}else//特殊方格不在棋盤的左下角{Borad[tr+s][tc+s-1]=t;ChessBoard(tr + s, tc, tr+s, tc+s-1, s);}if( tr+s <= dr && tc+s <= dc )//特殊方格在棋盤的右下角{ChessBoard(tr + s, tc + s, dr, dc, s);}else//特殊方格不在棋盤的右下角{Borad[tr + s][tc + s]=t;ChessBoard(tr + s, tc + s, tr+s, tc+s, s);}} int main() {cout << "輸入K的值：";int k;cin >> k;int temp = 1;for (int i = 0; i < k;i++){temp = temp * 2;}int size = temp;int x, y;//存儲特殊點所在的行列cout << "輸入特殊點在的行,列：(表示特殊點的值為-1)：";cin >> x >> y;Borad[x][y] = -1;ChessBoard(0, 0, x, y, size);for (int i = 0; i < size;i++){for (int j = 0; j < size;j++){cout <<setw(4)<< Borad[i][j]<<" ";}cout << endl;}system("pause");}

上述算法中：
使用了一個二維數(shù)組Board[][]表示棋盤，Board[0][0]是棋盤左上角的方格，tile是算法中的一個全局變量，用來表示L型骨牌，其初始值為0。
tr:棋盤左上角方格的行號
tc:棋盤左上角方格的列號
dr:特殊方格的行號
dc:特殊方格的列號
size:size=2^k，
棋盤的規(guī)格=2^K* 2^K

標記的次序：

總結(jié)

以上是生活随笔為你收集整理的算法设计与分析——递归与分治策略——棋盘覆盖的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。