分治
分治，分而治之。将复杂的问题逐步划分为若干不相交的子问题，逐个击破后进行合并，得到最终的解。其步骤如下：
- 划分（divide）
- 解决（conquer）
- 合并（merge）
经典：棋盘覆盖问题
给定一个大小为$2^k\times 2^k$（$k\in N_+$）的白色棋盘，其中有一个格子是黑色的。下图为$k=2$即4的棋盘示例。
现在想用一种大小占三个小方格的形骨牌来覆盖整个棋盘，这种L形骨牌可以通过旋转得到下面四种形态：
注意，在覆盖的时候，骨牌之间不能相互覆盖，也不能覆盖初始状态下已经是黑色的那个格子。
请输出覆盖方案，下图是上面示例的覆盖方案（注：不同颜色只是用来区分不同的骨牌，与题意无关）。
问题的解
首先明确的是，该问题一定是有解的（不妨自己用数学归纳法证明一下）。而原问题其实是比较复杂的（很明显，棋盘较大，而仅给了一个特殊方格），因此考虑分治。
divide
如何将原问题划分为若干互不相交的子问题？很直观的想法是，将棋盘进行四等分。但是仅给出了一个特殊方格，因此这样四等分后并不能得到四个子问题。这时就需要用到给定的L形骨牌了：将L形骨牌放置于未出现特殊方格的三个等分区域中，这样使得其也出现了“特殊方格”，进而划分出四个互不相交的子问题。接下来考虑递归边界：极限情况为$2\times 2$的棋盘，再划分时，四个方格均为特殊方格了，于是，当棋盘为$1\times 1$时，递归终止。
conquer
merge
用区域的左下角坐标、右上角坐标和特殊点坐标表示该区域。以上图为例，则对于给定的区域$(
- $(
- $(
- $(
- $(
当判断出给定的特殊点$
完整的解题代码如下。
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
typedef pair<int, int> P;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
vector<P> vs;
bool comp(P p1, P p2) {
if(p1.first == p2.first) return p1.second < p2.second;
return p1.first < p2.first;
}
void cope(int x1, int y1, int x2, int y2, int x, int y) {
/*
* x1, y1为左下角坐标，x2, y2为右上角坐标
* x, y为特殊点坐标
*/
if(x1 == x2 && y1 == y2) return;
int midx = x1 + (x2 - x1) / 2;
int midy = y1 + (y2 - y1) / 2;
if(x >= x1 && x <= midx && y >= y1 && y <= midy) {
// 在左下方区域
vs.push_back({midx+1, midy+1});
cope(x1, y1, midx, midy, x, y);
cope(midx+1, y1, x2, midy, midx+1, midy);
cope(x1, midy+1, midx, y2, midx, midy+1);
cope(midx+1, midy+1, x2, y2, midx+1, midy+1);
} else if(x >= midx+1 && x <=x2 && y >= y1 && y <= midy) {
// 在右下方区域
vs.push_back({midx, midy+1});
cope(x1, y1, midx, midy, midx, midy);
cope(midx+1, y1, x2, midy, x, y);
cope(x1, midy+1, midx, y2, midx, midy+1);
cope(midx+1, midy+1, x2, y2, midx+1, midy+1);
} else if(x >= x1 && x <= midx && y >= midy+1 && y <= y2) {
// 在左上方区域
vs.push_back({midx+1, midy});
cope(x1, y1, midx, midy, midx, midy);
cope(midx+1, y1, x2, midy, midx+1, midy);
cope(x1, midy+1, midx, y2, x, y);
cope(midx+1, midy+1, x2, y2, midx+1, midy+1);
} else {
// 在右上方区域
vs.push_back({midx, midy});
cope(x1, y1, midx, midy, midx, midy);
cope(midx+1, y1, x2, midy, midx+1, midy);
cope(x1, midy+1, midx, y2, midx, midy+1);
cope(midx+1, midy+1, x2, y2, x, y);
}
}
int main(int argc, char** argv) {
int n, x0, y0;
cin>>n>>x0>>y0;
cope(1, 1, pow(2, n), pow(2, n), x0, y0);
sort(vs.begin(), vs.end(), comp);
for(vector<P>::iterator iter = vs.begin(); iter != vs.end(); iter++) {
cout<<iter->first<<" "<<iter->second<<endl;
}
return 0;
}
