题目

{% fold 点击显/隐题目 %}

相传在一个古老的阿拉伯国家里，有一座宫殿。宫殿里有个四四方方的格子迷宫，国王选择驸马的方法非常特殊，也非常简单：公主就站在其中一个方格子上，只要谁能用地毯将除公主站立的地方外的所有地方盖上，美丽漂亮聪慧的公主就是他的人了。公主这一个方格不能用地毯盖住，毯子的形状有所规定，只能有四种选择(如图2)：

并且每一方格只能用一层地毯，迷宫的大小为2的k次方见方的方形。当然，也不能让公主无限制的在那儿等，对吧？由于你使用的是计算机，所以实现时间为1秒。

输入共2行。 第一行：k，即给定被填补迷宫的大小为2^k（0第二行：x y，即给出公主所在方格的坐标（x为行坐标，y为列坐标），x和y之间有一个空格隔开。
将迷宫填补完整的方案：每一补（行）为 x y c (x，y为毯子拐角的行坐标和列坐标，c为使用毯子的形状，具体见上面的图1，毯子形状分别用1、2、3、4表示，x、y、c之间用一个空格隔开)。
3 3 33
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
{% endfold %}

题解

由于AOJ没有 Special Judge 因此下面的代码没有 AC

不管什么情况,显然

代码

{% fold 点击显/隐代码 %}```cpp 地毯填补问题 https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
//
#define debug
#include
///
#include
#include
#include
#include
using namespace std;

inline bool between(int l, int m, int r) { return l <= m && m <= r; }
//int ID = 0;

struct Point {
int x, y;
Point(int _x = 0, int _y = 0) : x(_x), y(_y) {}
bool operator==(const Point &rhs) const { return x == rhs.x && y == rhs.y; }
};
struct Area {
int x1, x2, y1, y2;
//int id;
Area(int _x1 = 0, int _x2 = 0, int _y1 = 0, int _y2 = 0) {
init(_x1, _x2, _y1, _y2);
// printf("A %d %d %d %d id:%d\n", x1, x2, y1, y2, id);
}
Area(int t[4]) {
init(t[0], t[1], t[2], t[3]);
// printf("B %d %d %d %d id:%d\n", x1, x2, y1, y2, id);
}
Area(const Area &rhs) {
init(rhs.x1, rhs.x2, rhs.y1, rhs.y2);
// printf("C %d %d %d %d id:%d\n", x1, x2, y1, y2, id);
}
//~Area() { printf("del %d %d %d %d id:%d\n", x1, x2, y1, y2, id); }
Area operator=(const Area rhs) {
init(rhs.x1, rhs.x2, rhs.y1, rhs.y2);
// printf("D %d %d %d %d id:%d\n", x1, x2, y1, y2, id);
return *this;
}

void init(int _x1 = 0, int _x2 = 0, int _y1 = 0, int _y2 = 0) {
    x1 = min(_x1, _x2);
    x2 = max(_x1, _x2);
    y1 = min(_y1, _y2);
    y2 = max(_y1, _y2);
    //id = ID++;
}

inline bool In(const Point p) const {
    return between(x1, p.x, x2) && between(y1, p.y, y2);
}
Area divide(int k) const {
    int midx = (x1 + x2) / 2;
    int midy = (y1 + y2) / 2;
    int t[4] = {x1, x2, y1, y2};
    if (k == 1) {
        t[1] = midx;
        t[3] = midy;
    } else if (k == 2) {
        t[1] = midx;
        t[2] = midy + 1;
    } else if (k == 3) {
        t[0] = midx + 1;
        t[3] = midy;
    } else { // k == 4
        t[0] = midx + 1;
        t[2] = midy + 1;
    }
    Area area(t);
    return area;
}
//获取区域方位角坐标
Point GetPoint(int k) const {
    Point t;
    if (k == 1)
        t = Point(x1, y1);
    else if (k == 2)
        t = Point(x1, y2);
    else if (k == 3)
        t = Point(x2, y1);
    else //  k == 4
        t = Point(x2, y2);

    return t;
}

};
void show(const Point &p, int k/, int deep/) {
// for (int i = 0; i < deep; i++)
// printf(" ");
// printf("%d %d %d\n", p.x, p.y, k);
printf("%d %d %d\n", p.x, p.y, k);
}

//通过左上顶点和方向获取拐角
Point GetCorner(const Point &p, int k) {
Point t;
if (k == 1)
t = Point(p.x + 1, p.y + 1);
else if (k == 2)
t = Point(p.x + 1, p.y);
else if (k == 3)
t = Point(p.x, p.y + 1);
else // k == 4
t = Point(p.x, p.y);
return t;
}
int pow(int a, int n) {
if (n == 0)
return 1;
if (n == 1)
return a;
return pow(a, n / 2) * pow(a, n - n / 2);
}

void dfs(Area area, Point p/, int deep/) {
// getchar();
// for (int i = 0; i < deep; i++)
// printf(" ");
// printf("Area: x1=%d x2=%d y1=%d y2=%d id=%d Point: (%d,%d)\n", area.x1,
// area.x2, area.y1, area.y2, area.id, p.x, p.y);

//递归终点
if (area.x2 - area.x1 == 1) {
    for (int i = 1; i <= 4; i++) {
        if (area.GetPoint(i) == p)
            show(GetCorner(Point((area.x1 + area.x2) / 2, (area.y1 + area.y2) / 2), i), i/*, deep*/);
    }
    return;
}

Area t;
for (int i = 1; i <= 4; i++) {
    t = area.divide(i);
    // printf("t %d %d %d %d id:%d\n", t.x1, t.x2, t.y1, t.y2, t.id);
    if (t.In(p)) {
        dfs(t, p/*, deep + 1*/);
        show(
            GetCorner(
                Point((area.x1 + area.x2) / 2, (area.y1 + area.y2) / 2), i), i/*, deep*/);
    } else {
        dfs(t, t.GetPoint(5 - i)/*, deep + 1*/);
    }
}

}

int main() {
#ifdef debug
freopen("in.txt", "r", stdin);
int START = clock();
#endif
freopen("out.txt", "w", stdout);
cin.tie(0);
cin.sync_with_stdio(false);

int k, x, y;
while (scanf("%d%d%d", &k, &x, &y) != EOF) {
    Area area = Area(1, pow(2, k), 1, pow(2, k));
    Point point = Point(x, y);
    dfs(area, point/*, 0*/);
}

#ifdef debug
printf("Time:%.3fs.\n", double(clock() - START) / CLOCKS_PER_SEC);
#endif
return 0;
}

{% endfold %}