棋盤問題C++實作與分析

棋盤覆寫問題分析

前言：如果你想通過這篇文章了解 解題思路 那么你來對地方了，當然 借鑒 分析代碼也是可以的，文章最后我會附上完整的代碼，（如果對你有幫助請點個贊，原創不容易，碼字太累了）

（1）問題描述：在一個2^k * 2^{k（k為正整數，k<=10，length=2}k）個方格組成的棋盤中，恰有一個方格與其他方格不同，稱該方格為一特殊方格（其坐標為aa,bb，分別代表行坐標號和列坐標號），以及有四種L型骨牌（如下圖），求用若干塊這種L型骨牌實作除該特殊點棋盤的全覆寫，

輸入格式： 輸入三個數，分別是aa,bb,length.

輸出格式： 輸出整個棋盤，其中特殊方格填為0，然后鋪棋盤的順序為：先鋪四個子棋盤交界的部分，然后遞回的對每個子棋盤按照左上，右上，右下，左下的順時針順序鋪滿棋盤，每一塊骨牌中三個方格數字相同，按照順序標號，即第一塊骨牌全標為1，第二塊骨牌全標為2，…，以此類推，輸出的每個數占4個場寬，右對齊，

輸入樣例：
1 1 4

表示：特殊格子為（1，1），棋盤有4行4列

輸出樣例：
0 2 3 3
2 2 1 3
5 1 1 4
5 5 4 4

表示：先鋪三個1（一塊L型骨牌），再鋪三個2，…，最后鋪三個5，

解題思路：

這道題可以用 遞回 和 分而治之 的方法來做，先來看看要遞回啥，

（1) 遞回：以該圖可以觀察到，這是一個 8 X 8 的方格陣，根據題目要求方格陣大小是 2^k * 2^k（k為正整數，k<=10，length=2k），我們可以把大的方格陣從中心邊界不斷的等分為4份，直到方格陣長度為1，所以我們要遞回的目的就是在一個更小的方格陣內根據特殊點的位置判斷應該用哪一種L骨牌去處理，

(2) 分而治之：先看一個 4 X 4 的方格紙，發現特殊點只能是四個區域的一個，根據特殊點在中心邊界的右上，右下，左下，左上方分別用4種 對應的L骨牌 去處理，

回到之前的圖，我們確定中心邊界后發現特殊點在左上方所以用最后一種L骨牌去處理，

當處理完之后，把這 L骨牌占的3個點也當作特殊點 和之前的特殊點一起按照順序處理左上，右上，右下，左下的小方格陣的方法呼叫遞回函式，

（3）以左上方的區域為例，一步一步的分析下看是否符合我們的想法，

在 4 X 4 方格陣的中心邊界處發現特殊點在右下角，所以用第二種骨牌處理，按照上面的方法然后再呼叫遞回函式，

（4）在4個 2 X 2 方格陣里判斷特殊點的位置再用骨牌處理，分別得到下圖4個 2 X 2 方格陣，

（5）所以對于 8 X 8 方格來說左上角處理完后的 4 X 4 方格陣是這樣的，

代碼分析：

（1）先根據輸入的長度length和特殊點的坐標創建一個二維的容器，這里之所以是 <=length 是不用第0行和第0列；

for(int i=0;i<=length;i++){
	vector<int> newVecInt;
	vec.push_back(newVecInt);
	for(int j=0;j<=length;j++){
		vec[i].push_back(0);
	}
}
vec[aa][bb]=0;

（2）4個if陳述句來判斷特殊點在中心邊界的那個區域，
新增的兩個變數 curRow 和 curCol 分別是當前這個方格陣的起始坐標，例如對于4個 4 X 4 方格陣來說他們的當前行分別如圖示，作用是根據點的位置來確定L骨牌應該放的位置
以 8 X 8 為例，特殊點(4,4)，當前行列是1，1（因為第一次呼叫函式時的引數是handle(aa,bb,length,1,1)）
以中心點為基準來判斷可以算出坐標：(curRow + length/2 - 1，curCol + length/2 - 1)=(4,4）
此時特殊點在中心點上說明是在左上方（這里看代碼注釋）

void handle(int aa,int bb,int length,int curRow,int curCol){ 
	if(length==1)//最小的棋盤
		return; 
	if(aa<=curRow+length/2-1 && bb<=curCol+length/2-1){//點在左上角
	}
	if(aa<=curRow+length/2-1 && bb>curCol+length/2-1){//點在右上角
	}
	if(aa>curRow+length/2-1 && bb<=curCol+length/2-1){//點在左下角
	}
	if(aa>curRow+length/2-1 && bb>curCol+length/2-1){//點在右下角
	}
}

（3）我們在這個if陳述句里我們加入對應的L骨牌（這里cnt初始化為1）為了加入L方塊需要更改當前curRow和curCol，此時（curRow，curCol）=（2，2）,對(2,2)、(3,2)、(2,3)的完成賦值，再將次數加1 （這里tempRow和tempCol用來保存未變更之前的行列，之后有用）

	int tempRow=curRow;
	int tempCol=curCol;
	curRow=length/2+curRow-1;
	curCol=length/2+curCol-1;
	vec[curRow][curCol] = cnt;
	vec[curRow+1][curCol]=cnt;
	vec[curRow][curCol+1]=cnt;
	cnt++;

（4）弄好L骨牌后，就要按照順序依次弄左上，右上，右下，左下的小方格陣，為了確定每個方格陣的起始行列就要用到之前的tempRow/Col，稍微做一點運算就確定好了，前兩個引數我們把之前賦值的L骨牌位置當作特殊點傳遞，這里注意第三行代碼他的前兩個引數是aa，bb，這里我們看上圖的藍色點位置，就明白了，（這4行代碼可以根據上圖結合第三步給出的引數值分析）

	handle(curRow,curCol,length/2,tempRow,tempCol);//左上 
	handle(curRow,curCol+1,length/2,tempRow,curCol+1);//右上 
	handle(aa,bb,length/2,curRow+1,curCol+1);//右下 
	handle(curRow+1,curCol,length/2,curRow+1,tempCol);//左下

完整代碼：

上面給出的代碼是其中一種情況的處理，4個區域因此有4種處理，對每一種稍微做點修改就好了， 下面給出完整代碼：

//@copyright pclglutrjc1
#include<iostream>
#include<algorithm>
#include<vector>
#include<iomanip>
using namespace std;
int cnt=1;
vector<vector<int> >vec;
void handle(int aa,int bb,int length,int curRow,int curCol){ 
	if(length==1)
		return;//最小的棋盤 
									//特殊點在左上角的小棋盤
	if(aa<=curRow+length/2-1 && bb<=curCol+length/2-1){ 
		int tempRow=curRow;
		int tempCol=curCol;
		curRow=length/2+curRow;
		curCol=length/2+curCol;
		vec[curRow][curCol] = cnt;
		vec[curRow-1][curCol]=cnt;
		vec[curRow][curCol-1]=cnt;
		cnt++;
		handle(aa,bb,length/2,tempRow,tempCol);//左上 
		handle(curRow-1,curCol,length/2,tempRow,curCol);//右上 
		handle(curRow,curCol,length/2,curRow,curCol);//右下 
		handle(curRow,curCol-1,length/2,curRow,tempCol);//左下 
	}
	if(aa<=curRow+length/2-1 && bb>curCol+length/2-1){//特殊點在右上角的小棋盤
		int tempRow=curRow;
		int tempCol=curCol;
		curRow=length/2+curRow;
		curCol=length/2+curCol-1;
		vec[curRow][curCol] = cnt;
		vec[curRow-1][curCol]=cnt;
		vec[curRow][curCol+1]=cnt;
		cnt++;
		handle(curRow-1,curCol,length/2,tempRow,tempCol);//左上 
		handle(aa,bb,length/2,tempRow,curCol+1);//右上 
		handle(curRow,curCol+1,length/2,curRow,curCol+1);//右下 
		handle(curRow,curCol,length/2,curRow,tempCol);//左下 
	}
	if(aa>curRow+length/2-1 && bb<=curCol+length/2-1){//特殊點在左下角的小棋盤 
		int tempRow=curRow;
		int tempCol=curCol;
		curRow=length/2+curRow-1;
		curCol=length/2+curCol;
		vec[curRow][curCol] = cnt;
		vec[curRow][curCol-1]=cnt;
		vec[curRow+1][curCol]=cnt;
		cnt++;
		handle(curRow,curCol-1,length/2,tempRow,tempCol);//左上 
		handle(curRow,curCol,length/2,tempRow,curCol);//右上 
		handle(curRow+1,curCol,length/2,curRow+1,curCol);//右下 
		handle(aa,bb,length/2,curRow+1,tempCol);//左下 
	}
	if(aa>curRow+length/2-1 && bb>curCol+length/2-1){//特殊點在右下角的小棋盤 
		
		int tempRow=curRow;
		int tempCol=curCol;
		curRow=length/2+curRow-1;
		curCol=length/2+curCol-1;
		vec[curRow][curCol] = cnt;
		vec[curRow+1][curCol]=cnt;
		vec[curRow][curCol+1]=cnt;
		
		cnt++;
		handle(curRow,curCol,length/2,tempRow,tempCol);//左上 
		handle(curRow,curCol+1,length/2,tempRow,curCol+1);//右上 
		handle(aa,bb,length/2,curRow+1,curCol+1);//右下 
		handle(curRow+1,curCol,length/2,curRow+1,tempCol);//左下 
	}
	
}
int main(){
	int aa,bb,length;
	cin>>aa>>bb>>length;
	//對棋局初始化 
	for(int i=0;i<=length;i++){
		vector<int> newVecInt;
		vec.push_back(newVecInt);
		for(int j=0;j<=length;j++){
			vec[i].push_back(0);
		}
	}
	vec[aa][bb]=0;

	handle(aa,bb,length,1,1);
	for(int i=1;i<=length;i++){
		for(int j=1;j<=length;j++){
			cout<<setiosflags(ios::right)<<setw(4)<<vec[i][j];
			if(j==length)
				cout<<'\n';
		}
	}
	return 0;
}

效果截圖：