UVa 11134 Fabled Rooks ——区间选点

UVa 11134 Fabled Rooks ——区间选点

先将二维问题转化为两个一维问题

对于每个一维问题，将其进行排序，先将右端点从小到大排序，右端点相同将左端点从小到大排序

#include #include #include #include using namespace std;const int maxn = 5000 + 10;struct Node { int x1, y1, x2, y2; int id;}node[maxn];struct Ans { int x, y;}ans[maxn];int n, vis[maxn];bool cmp1(const Node &a, const Node &b) { if (a.x2 != b.x2) return a.x2 < b.x2; else return a.x1 < b.x1;}bool cmp2(const Node &a, const Node &b) { if (a.y2 != b.y2) return a.y2 < b.y2; else return a.y1 < b.y1;}int main(){ while (scanf("%d", &n) == 1 && n) { for (int i = 0; i < n; i++) { scanf("%d %d %d %d", &node[i].x1, &node[i].y1, &node[i].x2, &node[i].y2); node[i].x1--, node[i].y1--;//转化为【） node[i].id = i; } bool ok = true; memset(vis, 0, sizeof(vis)); sort(node, node + n, cmp1); for (int i = 0; i < n; i++) { bool error = true; for (int j = node[i].x1; j < node[i].x2; j++) { if (!vis[j]) { vis[j] = 1; ans[node[i].id].x = j; error = false; break; } } if (error) { ok = false; break; } } memset(vis, 0, sizeof(vis)); sort(node, node + n, cmp2); for (int i = 0; i < n; i++) { bool error = true; for (int j = node[i].y1; j < node[i].y2; j++) { if (!vis[j]) { vis[j] = 1; ans[node[i].id].y = j; error = false; break; } } if (error) { ok = false; break; } } if (ok) { for (int i = 0; i < n; i++) { printf("%d %d\n", ans[i].x + 1, ans[i].y + 1); } } else printf("IMPOSSIBLE\n"); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。