c语言--分治法经典例题--求解棋盘覆盖问题

问题描述：

        有一个2^k*2^k的正方形棋盘，在其内部有一个特殊方格标记为0，现在要用L形状的骨牌来覆盖除了特殊方格外的全部期盼，骨牌可以任意旋转但不能重叠。

求解：

        基本思想利用分治把棋盘等分为四块，利用每一块的左上角坐标（tx，ty）与特殊方块坐标（x，y）来进行判断，假如特殊方块在左上的区域内，就填充属于其他三个区域最对角的方块，如左上就填充这个区域的最有下的方块，左下就填充这个区域的最右上方块，看图好理解些。

        其实这三个区域的填充部分就是为了将红色区域充当每个区域的特殊方块，好让各自递归的执行下去（所谓的没有条件也要创造条件上：）），当执行到size==1（size为边长）时因就剩一个方格就不需要进行操作，可以直接return了。

        这里为什么size==1就直接返回而不是进行填充，是因为填充的这一步操作在每一个if-else的else里面已经执行了，第一句就是。

        number的值是用来充当不同的L型骨牌.

         这里的method方法就是主要的代码，因为依次检查四个区域属于重复性操作，所以这里就解释第一个if—else。

	if (x < tx + size && y < ty + size)
		method(b, tx, ty, x, y, size);
	else {
		b[tx + size - 1][ty + size - 1] = number;
		method(b, tx, ty, x + size - 1, y + size - 1, size);
	}

        第一个if—else检查的是当前的左上的区域，tx+size与ty+size含义就是前两行以及前两列，如果特殊方格在前两行与前两列的交汇处，那么就是在第一象限的里面，这时直接交给下一次递归。

        直接来看递归的倒数第二次，也就是只有四个方格的情况，按照四个if的顺序，代码会依次按照序号顺序检查方格，如果0方格不在这四个放个内，那么就会填充每个区域的对角方格由于这里每个区域只有一个方格，那么他填充的就是自己。 

完整代码如下：

#include
#include
using namespace std;

#define max 16
void show(int b[max][max], int size) {
	for (int i = 0; i < size; i++) {
		for (int j = 0; j < size; j++)
			cout << b[i][j] << " ";
		cout << endl;
	}
	cout << endl;
}

int numbernumber = 1;
void method(int b[max][max],int tx, int ty, int x, int y, int size) {
	if (size == 1) {//size等于2^k,只有一个方格就不需要进行操作
		show(b, max);
		return;
	}
	size /= 2;
	int number = numbernumber++;
	//tx,ty一直是0，0
	if (x < tx + size && y < ty + size)
		method(b, tx, ty, x, y, size);
	else {
		b[tx + size - 1][ty + size - 1] = number;
		method(b, tx, ty, x + size - 1, y + size - 1, size);
	}
	if (x < tx + size && y >= ty + size)
		method(b, tx, ty + size, x, y, size);
	else {
		b[tx + size - 1][ty + size] = number;
		method(b, tx, ty + size, tx + size - 1, ty + size, size);
	}
	if (x >= tx + size && y < ty + size)
		method(b, tx + size, ty, x, y, size);
	else {
		b[tx + size][ty + size - 1] = number;
		method(b, tx + size, ty, tx + size, ty + size - 1, size);
	}
	if (x >= tx + size && y >= ty + size)
		method(b, tx + size, ty + size, x, y, size);
	else {
		b[tx + size][ty + size] = number;
		method(b, tx + size, ty + size, tx + size, ty + size, size);
	}
}

int main() {
	int board[max][max];
	memset(board, -1, sizeof(board));
	board[1][1] = 0;
	int size = max;
	int number = 1;
	method(board, 0, 0, 1, 1, size);
	return 0;
}