【题目来源】
洛谷：P1228 地毯填补问题 - 洛谷 (luogu.com.cn)
【题目描述】
相传在一个古老的阿拉伯国家里，有一座宫殿。宫殿里有个四四方方的格子迷宫，国王选择驸马的方法非常特殊，也非常简单：公主就站在其中一个方格子上，只要谁能用地毯将除公主站立的地方外的所有地方盖上，美丽漂亮聪慧的公主就是他的人了。公主这一个方格不能用地毯盖住，毯子的形状有所规定，只能有四种选择（如图）：
并且每一方格只能用一层地毯，迷宫的大小为 \(2^k\times2^k\) 的方形。当然，也不能让公主无限制的在那儿等，对吧？由于你使用的是计算机，所以实现时间为 \(1\) 秒。
【输入】
输入文件共 \(2\) 行。
第一行一个整数 k，即给定被填补迷宫的大小为 \(2^k\times 2^k(0\lt k\le10)\)； 第二行两个整数 \(x,y\)，即给出公主所在方格的坐标（\(x\) 为行坐标，\(y\) 为列坐标），\(x\) 和 \(y\) 之间有一个空格隔开。
【输出】
将迷宫填补完整的方案：每一补（行）为 \(x\ y\ c\)（\(x,y\) 为毯子拐角的行坐标和列坐标，\(c\) 为使用毯子的形状，具体见上面的图 \(1\)，毯子形状分别用 \(1,2,3,4\) 表示，\(x,y,c\) 之间用一个空格隔开）。
【输入样例】
3
3 3
【输出样例】
5 5 1
2 2 4
1 1 4
1 4 3
4 1 2
4 4 1
2 7 3
1 5 4
1 8 3
3 6 3
4 8 1
7 2 2
5 1 4
6 3 2
8 1 2
8 4 1
7 7 1
6 6 1
5 8 3
8 5 2
8 8 1
【解题思路】
【算法标签】
《洛谷 P1228 地毯填补问题》 #递归# #分治# #Special judge#
【代码详解】
#include <bits/stdc++.h>
using namespace std;// 递归函数，用于填充棋盘
// (x,y): 当前棋盘区域的左上角坐标
// (gx,gy): 特殊方格的坐标
// l: 当前棋盘区域的边长
void f(int x, int y, int gx, int gy, int l)
{// 基本情况：棋盘大小为1时直接返回if (l == 1) return;// 情况1：特殊方格在左上象限if (gx <= x + l/2 - 1 && gy <= y + l/2 - 1) {// 在中心位置放置L型骨牌（类型1）cout << x + l/2 << " " << y + l/2 << " " << 1 << endl;// 递归处理四个子区域f(x, y, gx, gy, l/2); // 左上f(x, y + l/2, x + l/2 - 1, y + l/2, l/2); // 右上f(x + l/2, y, x + l/2, y + l/2 - 1, l/2); // 左下f(x + l/2, y + l/2, x + l/2, y + l/2, l/2); // 右下}// 情况2：特殊方格在右上象限else if (gx <= x + l/2 - 1 && gy >= y + l/2) {// 在中心位置放置L型骨牌（类型2）cout << x + l/2 << " " << y + l/2 - 1 << " " << 2 << endl;f(x, y, x + l/2 - 1, y + l/2 - 1, l/2); // 左上f(x, y + l/2, gx, gy, l/2); // 右上f(x + l/2, y, x + l/2, y + l/2 - 1, l/2); // 左下f(x + l/2, y + l/2, x + l/2, y + l/2, l/2); // 右下}// 情况3：特殊方格在左下象限else if (gx >= x + l/2 && gy <= y + l/2 - 1) {// 在中心位置放置L型骨牌（类型3）cout << x + l/2 - 1 << " " << y + l/2 << " " << 3 << endl;f(x, y, x + l/2 - 1, y + l/2 - 1, l/2); // 左上f(x, y + l/2, x + l/2 - 1, y + l/2, l/2); // 右上f(x + l/2, y, gx, gy, l/2); // 左下f(x + l/2, y + l/2, x + l/2, y + l/2, l/2); // 右下}// 情况4：特殊方格在右下象限else if (gx >= x + l/2 && gy >= y + l/2) {// 在中心位置放置L型骨牌（类型4）cout << x + l/2 - 1 << " " << y + l/2 - 1 << " " << 4 << endl;f(x, y, x + l/2 - 1, y + l/2 - 1, l/2); // 左上f(x, y + l/2, x + l/2 - 1, y + l/2, l/2); // 右上f(x + l/2, y, x + l/2, y + l/2 - 1, l/2); // 左下f(x + l/2, y + l/2, gx, gy, l/2); // 右下}
}int main()
{int k, x, y; // k: 棋盘大小为2^k × 2^k, (x,y): 特殊方格坐标cin >> k >> x >> y;// 调用递归函数，从(1,1)开始，棋盘大小为2^kf(1, 1, x, y, pow(2, k));return 0;
}
【运行结果】
3
3 3
5 5 1
2 2 4
1 1 4
1 4 3
4 1 2
4 4 1
2 7 3
1 5 4
1 8 3
3 6 3
4 8 1
7 2 2
5 1 4
6 3 2
8 1 2
8 4 1
7 7 1
6 6 1
5 8 3
8 5 2
8 8 1