首页 > 代码库 > UVA 1493 - Draw a Mess(并查集)
UVA 1493 - Draw a Mess(并查集)
UVA 1493 - Draw a Mess
题目链接
题意:在一个n*m平面上,有4种操作,对应把相应区域颜色涂成v(1<= v <= 9),现在经过q次操作以后,要求9种颜色各有多少个
思路:并查集,由于颜色涂上去会覆盖,这样我们就可以反向执行操作,这样保证每次操作如果之前有颜色就不能涂,如果没有就可以涂,然后一共有200行,每行都利用并查集压缩路径,查找下一个能涂色的位置即可
题目中说三角形边一定是奇数,可居然有偶数的。。。被这个坑了
代码:
#include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> using namespace std; const int N = 205; const int M = 50005; struct OP { int c, xc, yc, a, b, v; OP(){} OP(int c, int xc, int yc, int a, int b, int v) { this->c = c; this->xc = xc; this->yc = yc; this->a = a; this->b = b; this->v = v; } } op[M]; int parent[N][M]; int find(int *parent, int x) { return parent[x] == x ? x : parent[x] = find(parent, parent[x]); } int n, m, q, ans[10]; void init() { for (int i = 0; i < n; i++) for (int j = 0; j <= m; j++) parent[i][j] = j; memset(ans, 0, sizeof(ans)); char str[15]; int a, b, c, d, e; for (int i = 0; i < q; i++) { scanf("%s", str); scanf("%d%d%d%d", &a, &b, &c, &d); if (str[0] == 'C') op[i] = OP(0, a, b, c, 0, d); if (str[0] == 'D') op[i] = OP(1, a, b, c, 0, d); if (str[0] == 'R') { scanf("%d", &e); op[i] = OP(2, a, b, c, d, e); } if (str[0] == 'T') op[i] = OP(3, a, b, c, 0, d); } } void gao(int l, int r, int *parent, int v) { l = find(parent, l); while (l <= r) { ans[v]++; int tmp = find(parent, l + 1); parent[l] = tmp; l = tmp; } } void cir(int xc, int yc, int r, int v) { for (int i = max(0, xc - r); i <= min(n - 1, xc + r); i++) { int len = (int)(sqrt((r * r - (i - xc) * (i - xc)))); int l = max(0, yc - len), r = min(m - 1, yc + len); gao(l, r, parent[i], v); } } void dia(int xc, int yc , int r, int v) { for (int i = max(0, xc - r); i <= min(n - 1, xc + r); i++) { int len = r - abs(i - xc); int l = max(0, yc - len), r = min(m - 1, yc + len); gao(l, r, parent[i], v); } } void rec(int xc, int yc, int h, int w, int v) { for (int i = max(0, xc); i <= min(n - 1, xc + h - 1); i++) { int l = max(0, yc), r = min(m - 1, yc + w - 1); gao(l, r, parent[i], v); } } void tri(int xc, int yc, int w, int v) { for (int i = max(0, xc); i <= min(n - 1, xc + (w + 1) / 2 - 1); i++) { int len = (w - 1) / 2 - i + xc; int l = max(0, yc - len), r = min(m - 1, yc + len); gao(l, r, parent[i], v); } } void solve() { for (int i = q - 1; i >= 0; i--) { if (op[i].c == 0) cir(op[i].xc, op[i].yc, op[i].a, op[i].v); if (op[i].c == 1) dia(op[i].xc, op[i].yc, op[i].a, op[i].v); if (op[i].c == 2) rec(op[i].xc, op[i].yc, op[i].a, op[i].b, op[i].v); if (op[i].c == 3) tri(op[i].xc, op[i].yc, op[i].a, op[i].v); } for (int i = 1; i <= 9; i++) printf("%d%c", ans[i], i == 9 ? '\n' : ' '); } int main() { while (~scanf("%d%d%d", &n, &m, &q)) { init(); solve(); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。