棋盘覆盖问题 C++实现11

具体问题陈述和相关解说可以参照百度百科：

http://baike.baidu.com/link?url=Tk1lkOLnZ3ofYRYiLOCtvIk0MIcvgDCpF1Ab5TmZUs2fKXy2kS-mvRKo992tx6QlayP7s4vqqxmoipPSXCrwlq

但我发现，百度百科的说明和《算法设计与分析》这本书是一样的，错的地方还是一样的错。

到底出处是哪里？是谁抄谁的还是都是抄别人的，那就不得而知了。

本博客不会这样照搬复述的，本博客的文章都是自己的理解总结出来，和自己思考所得的结论，最多包含某些书本的精要概括，绝对原创，要引用本博客内容的朋友请注明出处。

这里就指出重点和难点加以分析。并改正其错误。

这里就不复述问题了，简单来说就是利用L型的骨牌，填充2^k*2^k的方形棋盘。其中棋盘用2维数组表示，这里用vector<vector<int> > board表示。

解决这个问题的方法也是分治法，需要用到递归，重点难点如下：

1. 递归问题的思考应该从最小问题开始，比如这道题就应该从a[2][2]这个最小规模的问题思考起来，然后当数组更加大的时候，情况也是一样的。大家可以看做这个是思考的突破口！如果实在难以理解，只能是用[4][[4]这样大一点的棋盘，画图，然后一步一步，一个递归一个递归层地区手动走一走程序了。之所以难理解是因为它有四个分支递归，因为分了四个区域。

2. 这道题的填充的是由3个格组成的L型骨牌，注意的就是这个骨牌要想象成为是可以拆分成3个格分别填充的。只要最后组成了一个一个完整的L型骨牌就算符合要求了。

勘误：主要是填的骨牌序号问题，那个需要用一个stack来保存，才能保证所填的序号无误。一般书上都不用栈，会导致填充不正确。

其他的且看程序详细注解：

#include<iostream>
#include<vector>
#include<stack>

using namespace std;

vector<vector<int> > board(4);//棋盘数组，也可以作为参数传递进chessBoard中去，作为全局变量可以减少参数传递
stack<int> stI;	//记录当前所使用的骨牌号码，使用栈顶元素填充棋盘数组
int sL = 0;		//L型骨牌序号

//所有下标皆为0开始的C C++下标
void chessBoard(int uRow, int lCol, int specPosR, int specPosC, int rowSize)
{
	if(rowSize ==1) return;
	//static int sL = 0;棋牌和骨牌都可以用static代替，如果不喜欢用全局变量的话。
	sL++;	
	stI.push(sL); //每递归深入一层，就把一个骨牌序号入栈
	int halfSize = rowSize/2;//拆分

	//注意：下面四个if else，肯定是只有一个if成立，然后执行if句，而肯定有三个else语句要执行的，因为肯定有一个是特殊位置，而其他三个是空白位置，需要填充骨牌。

	//1如果特殊位置在左上角区域，则继续递归，直到剩下一个格子，并且该格子已经填充，遇到函数头一句if(rowSize == 1) return;就跳出一层递归。
	//注意是一个区域或子棋盘，有一个或者多个格子，并不是就指一个格子。
	if(specPosR<uRow+halfSize && specPosC<lCol+halfSize)
		chessBoard(uRow, lCol, specPosR, specPosC, halfSize);
	//如果其他情况
	else
	{
		board[uRow+halfSize-1][lCol+halfSize-1] = stI.top();
		//因为特殊位置不在，所以可以选择任意一个空格填充，但是本算法只填充左上角（也许不止一个格，也许有很多个格子）区域的右下角。大家仔细查一下，就知道下标[uRow+halfSize-1][lCol+halfSize-1]是本区域中最右下角的一个格子的下标号。
		chessBoard(uRow, lCol, uRow+halfSize-1, lCol+halfSize-1, halfSize);
		//然后是递归填充这个区域的其他空白格子。因为上一句已经填充了[uRow+halfSize-1][lCol+halfSize-1]这个格子，所以，这个下标作为特殊位置参数传递进chessBoard中。
	}	

	//2右上角区域，解析类上
	if(specPosR<uRow+halfSize && specPosC>=lCol+halfSize)
		chessBoard(uRow, lCol+halfSize, specPosR, specPosC, halfSize);
	else
	{
		board[uRow+halfSize-1][lCol+halfSize] = stI.top();
		chessBoard(uRow, lCol+halfSize, uRow+halfSize-1, lCol+halfSize, halfSize);
	}		

	//3左下角区域，类上
	if(specPosR>=uRow+halfSize && specPosC<lCol+halfSize)
		chessBoard(uRow+halfSize, lCol, specPosR, specPosC, halfSize);
	else
	{
		board[uRow+halfSize][lCol+halfSize-1] = stI.top();
		chessBoard(uRow+halfSize, lCol, uRow+halfSize, lCol+halfSize-1, halfSize);
	}	

	//4右下角区域，类上
	if(specPosR>=uRow+halfSize && specPosC>=lCol+halfSize)
		chessBoard(uRow+halfSize, lCol+halfSize, specPosR, specPosC, halfSize);
	else
	{
		board[uRow+halfSize][lCol+halfSize] = stI.top();
		chessBoard(uRow+halfSize, lCol+halfSize, uRow+halfSize, lCol+halfSize, halfSize);
	}	

	stI.pop();//本次骨牌号填充了三个格，填充完就出栈
}

void test()
{
	//初始化数组
	for(int i=0; i<4; i++)
	{
		board[i].resize(4);
	}

	chessBoard(0, 0, 3, 3, 4);

	//特殊位置填充0
	board[3][3] = 0;

	//序列输出
	for(int j=0; j<4; j++)
	{
		for(int i=0; i<4; i++)
			cout<<board[j][i]<<"\t";
		cout<<endl;
	}
	cout<<endl;
}


int main()
{
	test();
	return 0;
}

总结：

递归法的确很难，分治法应用递归就更加难了。思路要清晰，具体例子分析一下。

输出结果如图：