AOJ 859.地毯填补问题

250


题目



点击显/隐题目

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




题解


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



不管什么情况,显然


代码


点击显/隐代码
/*/
#define debug
#include <ctime>
//*/
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
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;
}
发布评论
  • 点击查看/关闭被识别为广告的评论