UVA1493 - Draw a Mess(并查集)

UVA1493 - Draw a Mess(并查集)

題目鏈接

題目大意:一個N * M 的矩陣，每次你在上面將某個范圍上色，不論上面有什么顏色都會被最新的顏色覆蓋，顏色是1-9，初始的顏色是0.最后輸出這個矩形中。每一個顏色有多少個。某個范圍這個分為了四種，圓，矩形，菱形，還有正三角形（倒著的）。注意這題的邊界，不能超出這個矩形，非常easy越界。

解題思路：由于題的矩陣范圍是200 * 50000，然后操作又是50000，這樣三個相乘，即使給60s也是不夠的。由于行的數目比較少。假設每次都能將這一行哪個沒處理過直接拿出來。而不用一個一個推斷就快非常多了，這樣一來就相當于每一個格子僅僅要遍歷一次。所以這里就每行用一個并查集。標記這這個位置以及后面的位置能夠上色的起始位置。

然后顏色更新問題僅僅要將操作反著過來上色就能夠處理了。

代碼：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>using namespace std;
const int M = 50005;
const int N = 205;int f[N][M];
int G[N][M];
int color[10];
int n, m, q;
char str[N];struct OP {char type;int x, y, l, r, c;
}op[M];int getParent (int x, int y) { return y == f[x][y] ?

y : f[x][y] = getParent (x, f[x][y]); } void init() { for (int i = q - 1; i >= 0; i--) { scanf ("%s", str); if (str[0] == 'D') scanf ("%d%d%d%d", &op[i].x, &op[i].y, &op[i].l, &op[i].c); else if (str[0] == 'T') scanf ("%d%d%d%d", &op[i].x, &op[i].y, &op[i].l, &op[i].c); else if (str[0] == 'R') scanf ("%d%d%d%d%d", &op[i].x, &op[i].y, &op[i].l, &op[i].r, &op[i].c); else scanf ("%d%d%d%d", &op[i].x, &op[i].y, &op[i].l, &op[i].c); op[i].type = str[0]; } for (int i = 0; i <= n; i++) for (int j = 0; j <= m; j++) f[i][j] = j; memset (color, 0, sizeof (color)); } void circle (int x, int y, int r, int c) { int L, R, s; for (int i = -r; i <= r; i++) { s = sqrt(r * r - i * i); if (i + x >= n || i + x < 0) continue; L = max(y - s, 0); L = max (getParent (i + x, L), L); R = min (s + y, m - 1); for (int j = L; j <= R; j++) { if (j == getParent (i + x, j)) { color[c]++; f[i + x][j] = R + 1; } else j = getParent(i + x, j) - 1; } } } void diamond (int x, int y, int r, int c) { int L, R; for (int i = -r; i <= r; i++) { if (i + x >= n || i + x < 0) continue; R = min (r - abs(i) + y, m - 1); L = max (abs(i) - r + y, 0); L = max (L, getParent (i + x, L)); for (int j = L; j <= R; j++) { if (j == getParent (i + x, j)) { color[c]++; f[i + x][j] = R + 1; } else j = getParent (i + x, j) - 1; } } } void rectangle (int x, int y, int l, int w, int c) { int L, R; for (int i = x; i < min(x + l, n); i++) { L = max (y, getParent (i, y)); R = min (y + w - 1, m - 1); for (int j = L; j <= R; j++) { if (j == getParent (i, j)) { color[c]++; f[i][j] = R + 1; } else j = getParent (i, j) - 1; } } } void triangle (int x, int y, int w, int c) { int L, R, h; h = (w + 1) / 2; for (int i = 0; i < h; i++) { if (i + x >= n) break; L = max (y - h + i + 1, 0); L = max (getParent(i + x, L), L); R = min (y + h - i - 1, m - 1); for (int j = L; j <= R; j++) { if (j == getParent (i + x, j)) { color[c]++; f[i + x][j] = R + 1; } else j = getParent (i + x, j) - 1; } } } void solve () { for (int i = 0; i < q; i++) { if (op[i].type == 'D') diamond (op[i].x, op[i].y, op[i].l, op[i].c); else if (op[i].type == 'C') circle (op[i].x , op[i].y, op[i].l, op[i].c); else if (op[i].type == 'T') triangle (op[i].x, op[i].y, op[i].l, op[i].c); else rectangle (op[i].x, op[i].y, op[i].l, op[i].r, op[i].c); } } int main () { char str[N]; while (scanf ("%d%d%d", &n, &m, &q) != EOF) { init (); solve(); for (int i = 1; i < 9; i++) printf ("%d ", color[i]); printf ("%d\n", color[9]); } return 0; }