原题链接：https://www.luogu.com.cn/problem/P1228
题意解读：用4种毯子铺满2^k * 2^k的区域，留出一个公主位置，输出所有毯子拐角的坐标以及哪种毯子，看起来有点无从下手，
可以从k=1，k=2，k=3入手去依次考虑，找到规律，用分治法解决。
解题思路：
1、当k=1时，即2*2的区域，对于任意一个位置是公主，都可以得到唯一一种铺设方案
2、当k=2时，即4*4的区域，对于任意一个位置是公主，如下图：
可以将4*4区域划分成4个2*2的区域
如果每个区域都有一个公主，问题就好解决了，因为右上区域有了公主，可以假设最中间的2*2区域的右上角有公主，先对这个区域进行铺设：
然后，把中间铺设的地毯都当做公主，这样就能保证4个2*2的区域都有了公主：
再分4个区域依次进行处理，问题就变成了k=1时的情况，即可得到上图的结果。
3、同理，当k=3时，即8*8的区域，对于任意位置是公主，如下图：
将8*8区域划分成4个4*4区域
根据公主所在的区域，对中间2*2区域进行铺设
这样，假设中间2*2铺设的毯子都是公主，则4个4*4区域就都有了公主
再依次对4个4*4区域进行处理，问题就变成了k=2时的情况，最终可以变成k=1时的情况，问题得解。
100分代码：
#include <bits/stdc++.h>
using namespace std;int k, x, y;//cover是铺地毯函数，(x1,y1)是左上角的坐标，(x2,y2)是右下角的坐标，(x,y)是公主的的坐标
void cover(int x1, int y1, int x2, int y2, int x, int y)
{if(x2 - x1 == 1) //2 * 2区域时{ //公主在左上角，用毯子1if(x1 == x && y1 == y) cout << x2 << " " << y2 << " " << 1 << endl; //公主在右上角，用毯子2else if(x1 == x && y2 == y) cout << x2 << " " << y1 << " " << 2 << endl;//公主在左下角，用毯子3else if(x2 == x && y1 == y) cout << x1 << " " << y2 << " " << 3 << endl;//公主在右下角，用毯子4else cout << x1 << " " << y1 << " " << 4 << endl;return;}//将2^k * 2^k区域分成4个2^(k-1) * 2^(k-1)的区域//计算公主在哪个区域，把正中间的2*2区域用一个地毯覆盖，这个地毯相当于让4个2^(k-1) * 2^(k-1)的区域都有一个公主//再递归处理int len = x2 - x1 + 1; //len是边长int half = len / 2; //half是边长的一半//中间2 * 2区域每个格子的坐标int xa = x1 + half - 1, ya = y1 + half - 1; //左上int xb = x1 + half - 1, yb = y1 + half; //右上int xc = x1 + half, yc = y1 + half - 1; //左下int xd = x1 + half, yd = y1 + half; //右下//公主在左上区域if(x >= x1 && x <= xa && y >= y1 && y <= ya) {//填补正中间2*2区域cover(xa, ya, xd, yd, xa, ya);//设定左上区域的公主位置xa = x, ya = y;}//公主在右上区域else if(x >= x1 && x <= xb && y >= yb && y <= y2){//填补正中间2*2区域cover(xa, ya, xd, yd, xb, yb);//设定右上区域的公主位置xb = x, yb = y;}//公主在左下区域else if(x >= xc && x <= x2 && y >= y1 && y <= yc){//填补正中间2*2区域cover(xa, ya, xd, yd, xc, yc);//设定左下区域的公主位置xc = x, yc = y;}//公主在右下区域else {//填补正中间2*2区域cover(xa, ya, xd, yd, xd, yd);//设定右下区域的公主位置xd = x, yd = y;}//递归处理4个2^(k-1) * 2^(k-1)的区域cover(x1, y1, x1 + half - 1, y1 + half - 1, xa, ya); //左上cover(x1, y1 + half, x1 + half - 1, y2, xb, yb); //右上cover(x1 + half, y1, x2, y1 + half - 1, xc, yc); //左下cover(x1 + half, y1 + half, x2, y2, xd, yd); //右下
}int main()
{cin >> k >> x >> y;cover(1, 1, 1 << k, 1 << k, x, y);return 0;
}
