程式碼分析+原理圖解——棋盤覆蓋問題-分治法

上演演算法課時，老師以文字+程式碼的方式講了這道題，然而有很多同學反映聽的不是太懂， 我們接觸事物最直觀的就是以圖片理解，因此我嘗試使用圖解法來幫助大家理解。

---

問題描述：

 

注意：分治法最核心的一點是：分出的子問題要與原問題性質相同

但不管我們怎麼分，只要這個奇異點在某一個子問題中， 這個子問題必定不與其他子問題相等。

如果將奇異點扣除再分，又無法等分成正方形棋盤。

因此，我們解決這道題的思路是：在沒有奇異點的子棋盤中，人為的構造奇異點，使其與有奇異點的子問題相同即可。

---

首先給出一個包含一個奇異點的16*16棋盤：

第一步是將該棋盤分為四個等大的子棋盤：

然後將該棋盤看做是4*4的棋盤，可以看到奇異點在左上角的子棋盤中，那麼這一步的任務就是用一個（真的是一個）L型的棋子（下圖中紅色的格子）將其他三個子棋盤構造成含奇異點的子棋盤：

下一步是將紅線分割的子棋盤又切割成四個子棋盤（白色線切開的子棋盤）：

然後對每個紅色線包圍在裡面的子棋盤，用一個L型棋子（黃色）又構造出奇異點，使得每個子棋盤都有一個奇異點，即白色線圍起來的格子看做是一個整體，裡面包含一個黃色的奇異點：

下一步是繼續講白色線包圍的格子切分為4個子棋盤，這裡為了方便觀察，將前面所有的分割線去掉：

同理，對黃色的棋盤構造含奇異點的子棋盤（藍色）：

最後可以分割到2*2的格子，然後每個2*2的子棋盤都已經包含一個奇異點了，剩下的就是用L型旗子去填好剩下的三個格子。

---

到此為止， 棋盤的分割就結束了。

那麼，如何將其轉化為程式碼實現呢？

輸入n(棋盤大小)、 奇異點座標、用不同數位代表不同的骨牌進行輸出。

執行結果如下圖所示：

 
接下來分析程式碼：

---

程式碼思路分析：

雖然理解了原理， 可是轉化為程式碼的歷程並非一帆風順， 要考慮很多的細節。

心路歷程：
最初是想要分別求出四種情況，判斷每種情況，並賦予不同的奇異點，但發現賦予奇異點後沒辦法用統一的分治迭代(因為每種情況的引數不同)，但若是每種情況下都去迭代四個分治，又太麻煩， 於是放棄。

搜網後， 發現主流的解法是：同樣用四個if判斷，但每個if判斷如果成立，直接分治；如果不成立，則轉到else中分治， 這樣只用了四個判斷，八個條件就解出了問題。大大提高了程式碼的複用性

注意：
不要被「棋盤」誤導，棋子並不是要放到棋盤邊界線上， 而是要將棋盤內空間看做點

---

程式碼展示

#include<iostream>
using namespace std;

int def[110][110];
static int t = 0;

void chess(int a, int b, int aa, int bb, int length) {
	if(length==1) return;
	t++;
	int tem = t;
	int l = length/2;
	if(aa<a+l && bb<b+l) chess(a,b,aa,bb,l);
	else {
		def[a+l-1][b+l-1] = tem;
		chess(a,b,a+l-1,b+l-1,l);
	}
	
	if(aa>=a+l && bb<b+l) chess(a+l,b,aa,bb,l);	//左下角棋盤
	else {
		def[a+l][b+l-1]=tem;
		chess(a+l,b,a+l,b+l-1,l);
	} 
	
	if(aa<a+l && bb>=b+l) chess(a,b+l,aa,bb,l);	//右上角的子棋盤
	else {
		def[a+l-1][b+l] = tem;
		chess(a,b+l,a+l-1,b+l,l);
	} 
	
	if(aa>=a+l && bb>=b+l) chess(a+l, b+l, aa, bb,l);
	else {
		def[a+l][b+l]=tem;
		chess(a+l, b+l, a+l, b+l, l);
	}
} 

int main() {
	int n, a, b, aa, bb, length, m;
	//a,b 是子棋盤左上角的行列號
	//aa,bb是特殊點的行列號
	cin>>length>>aa>>bb;
	a = b = 1;
	m = length;
	
	chess(a,b,aa,bb,length); 
	
	for(int i=1;i<=m;i++) //輸出結果
        for(int j=1;j<=m;j++){
            cout.width(3);
            cout<<def[i][j];
            if(j==m) cout<<endl;
        }
	return 0;
}

如果覺得還不錯，就請給博主一個贊吧！