首页 > ACM题库 > HDU-杭电 > HDU 4056-Draw a Mess-并查集-[解题报告]HOJ
2015
04-16

HDU 4056-Draw a Mess-并查集-[解题报告]HOJ

Draw a Mess

问题描述 :

It’s graduated season, every students should leave something on the wall, so….they draw a lot of geometry shape with different color.

When teacher come to see what happened, without getting angry, he was surprised by the talented achievement made by students. He found the wall full of color have a post-modern style so he want to have an in-depth research on it.

To simplify the problem, we divide the wall into n*m (1 ≤ n ≤ 200, 1 ≤ m ≤ 50000) pixels, and we have got the order of coming students who drawing on the wall. We found that all students draw four kinds of geometry shapes in total that is Diamond, Circle, Rectangle and Triangle. When a student draw a shape in pixel (i, j) with color c (1 ≤ c ≤ 9), no matter it is covered before, it will be covered by color c.

There are q (1 ≤ q ≤ 50000) students who have make a drawing one by one. And after q operation we want to know the amount of pixels covered by each color.

输入:

There are multiple test cases.

In the first line of each test case contains three integers n, m, q. The next q lines each line contains a string at first indicating the geometry shape:

* Circle: given xc, yc, r, c, and you should cover the pixels(x, y) which satisfied inequality (x – xc)2 + (y – yc)2 ≤ r2 with color c;
* Diamond: given xc, yc, r, c, and you should cover the pixels(x, y) which satisfied inequality abs(x – xc) + abs(y – yc) ≤ r with color c;
* Rectangle: given xc, yc, l, w, c, and you should cover the pixels(x, y) which satisfied xc ≤ x ≤ xc+l-1, yc ≤ y ≤ yc+w-1 with color c;
* Triangle: given xc, yc, w, c, W is the bottom length and is odd, the pixel(xc, yc) is the middle of the bottom. We define this triangle is isosceles and the height of this triangle is (w+1)/2, you should cover the correspond pixels with color c;

Note: all shape should not draw out of the n*m wall! You can get more details from the sample and hint. (0 ≤ xc, x ≤ n-1, 0 ≤ yc, y ≤ m-1)

输出:

There are multiple test cases.

In the first line of each test case contains three integers n, m, q. The next q lines each line contains a string at first indicating the geometry shape:

* Circle: given xc, yc, r, c, and you should cover the pixels(x, y) which satisfied inequality (x – xc)2 + (y – yc)2 ≤ r2 with color c;
* Diamond: given xc, yc, r, c, and you should cover the pixels(x, y) which satisfied inequality abs(x – xc) + abs(y – yc) ≤ r with color c;
* Rectangle: given xc, yc, l, w, c, and you should cover the pixels(x, y) which satisfied xc ≤ x ≤ xc+l-1, yc ≤ y ≤ yc+w-1 with color c;
* Triangle: given xc, yc, w, c, W is the bottom length and is odd, the pixel(xc, yc) is the middle of the bottom. We define this triangle is isosceles and the height of this triangle is (w+1)/2, you should cover the correspond pixels with color c;

Note: all shape should not draw out of the n*m wall! You can get more details from the sample and hint. (0 ≤ xc, x ≤ n-1, 0 ≤ yc, y ≤ m-1)

样例输入:

8 8 4
Diamond 3 3 1 1
Triangle 4 4 3 2
Rectangle 1 1 2 2 3
Circle 6 6 2 4

样例输出:

4 4 4 11 0 0 0 0 0

Hint
The final distribution of different colors: 00000000 03300000 03310000 00111000 00022240 00002444 00004444 00000444

这题用线段树写的话会很恶心人 并且不是现场赛的话,HDU上内存有限制

所以就是用并查集来搞这种涂色问题,并且效率上也快一些

这种方法之前也接触过  详见从acmol的空间看的http://blog.acmol.com/?p=751

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <cstdlib>
#include <ctime>
#define eps 1e-5
#define MAXN 111111
#define MAXM 1111111
#define INF 1000000008
using namespace std;
int fa[55555];
int ans[15];
struct P
{
    int a, b, c, x, y;
    char op[15];
}p[55555];
int vis[55555];
int find(int x)
{
    if(fa[x] == -1) return x;
    int t = find(fa[x]);
    fa[x] = t;
    return t;
}
int main()
{
    int n, m, q;
    while(scanf("%d%d%d", &n, &m, &q) != EOF)
    {
        memset(ans, 0, sizeof(ans));
        for(int i = 0; i < q; i++)
        {
            scanf("%s%d%d%d%d", p[i].op, &p[i].x, &p[i].y, &p[i].a, &p[i].b);
            if(p[i].op[0] == 'R') scanf("%d", &p[i].c);
        }
        for(int k = 0; k < n; k++)
        {
            for(int i = 0; i <= m; i++) fa[i] = -1, vis[i] = 0;
            for(int i = q - 1; i >= 0; i--)
            {
                int co = p[i].b, a, b;
                if(p[i].op[0] == 'R')
                {
                    co = p[i].c;
                    if(k < p[i].x || k >= p[i].x + p[i].a) continue;
                    a = p[i].y;
                    b = p[i].y + p[i].b - 1;
                }
                else if(p[i].op[0] == 'C')
                {
                    if(abs(k - p[i].x) > p[i].a) continue;
                    int tmp = p[i].a * p[i].a - (k - p[i].x) * (k - p[i].x);
                    int tp = (int)(sqrt(tmp));
                    a = p[i].y - tp;
                    b = p[i].y + tp;
                }
                else if(p[i].op[0] == 'D')
                {
                    if(abs(k - p[i].x) > p[i].a) continue;
                    int tmp = p[i].a - abs(k - p[i].x);
                    a = p[i].y - tmp;
                    b = p[i].y + tmp;
                }
                else if(p[i].op[0] == 'T')
                {
                    if(k - p[i].x >= (p[i].a + 1) / 2 || k < p[i].x) continue;
                    int tmp = (p[i].a - 1) / 2 - (k - p[i].x);
                    a = p[i].y - tmp;
                    b = p[i].y + tmp;
                }
                a = max(a, 0);
                b = min(m - 1, b);
                int fx = find(a), fy;
                for(int j = b; j >= a; j = fy - 1)
                {
                    fy = find(j);
                    if(!vis[fy]) ans[co]++;
                    vis[fy] = 1;
                    if(fx != fy) fa[fy] = fx;
                }
            }
        }
        for(int i = 1; i < 9; i++) printf("%d ", ans[i]);
        printf("%d\n", ans[9]);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/sdj222555/article/details/7946065