Artwork Gym - 101550A （并查集）

题目

https://cn.vjudge.net/problem/Gym-101550A

题意

问你没涂一次，白块分成多少份

思路

先都涂完，然后到这删除，没删除一块看合并的多少块

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3+10;
int mp[maxn][maxn];
int n,m,q;
int tx[4] = {0,0,1,-1};
int ty[4] = {1,-1,0,0};
int a[maxn*maxn];
int ans[maxn*10],anss;
int top;
int vis[maxn][maxn];

struct node
{
    int x1,x2,y1,y2;
    int x,y;
}qu[maxn*10];

int fin(int x)
{
    return a[x]==x?x:a[x]=fin(a[x]);
}

int get(int x,int y)
{
    return (x-1)*m +y;
}

void tu(int x)
{
    int x1 = qu[x].x1,x2 = qu[x].x2,y1 = qu[x].y1,y2 = qu[x].y2;
    if(x1 == x2)
    {
        for(int i = min(y1,y2);i <= max(y1,y2);i++)
        {
            mp[x1][i]++;
        }
    }
    else
    {
        for(int i = min(x1,x2);i <= max(x1,x2);i++)
        {
            mp[i][y1]++;
        }
    }
}

int ok(int x,int y)
{
    if(x<1||x>n||y<1||y>m) return 0;
    if(mp[x][y]) return 0;
    if(vis[x][y]) return 0;
    return 1;
}
void bfs(int sx,int sy,int fx)
{
    node u,v;
    u.x = sx,u.y = sy;
    vis[u.x][u.y] = 1;
    queue<node> q;
    q.push(u);
    while(!q.empty())
    {
        u = q.front();
        q.pop();
        for(int i = 0;i < 4;i++)
        {
            int dx = u.x + tx[i];
            int dy = u.y + ty[i];
            if(ok(dx,dy))
            {
                v.x = dx,v.y = dy;
                vis[v.x][v.y] = 1;
                q.push(v);
                int fy = get(dx,dy);
                a[fy] = fx;
            }
        }
    }
}

int okk(int x,int y)
{
    if(x<1||x>n||y<1||y>m) return 0;
    if(mp[x][y]) return 0;
    return 1;
}
int okkk(int x,int y)
{
    if(mp[x][y] > 0) return 1;
    return 0;
}
void shan(int id)
{
    int x1 = qu[id].x1,x2 = qu[id].x2,y1 = qu[id].y1,y2 = qu[id].y2;
    int f = 0;
    int fx,fy;
    if(x1 == x2)
    {
        for(int i = min(y1,y2);i <= max(y1,y2);i++)
        {
            int x = x1,y = i;
            mp[x][y]--;
            if(okkk(x,y)) continue;
            fx = fin(get(x,y));
            anss++;
            f = 1;
            for(int j = 0;j < 4;j++)
            {
                int dx = x + tx[j];
                int dy = y + ty[j];
                if(okk(dx,dy))
                {
                    int fy = fin(get(dx,dy));
                    if(fx != fy)
                    {
                        a[fy] = fx;
                        anss--;
                    }
                }
            }
        }
    }
    else
    {
        for(int i = min(x1,x2);i <= max(x1,x2);i++)
        {
            int x = i,y = y1;
            mp[x][y]--;
            if(okkk(x,y)) continue;
            fx = fin(get(x,y));
            anss++;
            f = 1;
            for(int j = 0;j < 4;j++)
            {
                int dx = x + tx[j];
                int dy = y + ty[j];
                if(okk(dx,dy))
                {
                    int fy = fin(get(dx,dy));
                    if(fx != fy)
                    {
                        a[fy] = fx;
                        anss--;
                    }
                }
            }
        }

    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&q);
    for(int i = 1;i <= n*m;i++)
    {
        a[i] = i;
    }

    for(int i = 1;i <= q;i++)
    {
        scanf("%d%d%d%d",&qu[i].x1,&qu[i].y1,&qu[i].x2,&qu[i].y2);
    }

    for(int i = 1;i <= q;i++)
    {
        tu(i);
    }
    top = 0;
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <= m;j++)
        {
            if(mp[i][j] == 0&&vis[i][j] == 0)
            {
                top++;
                int fx = get(i,j);
                bfs(i,j,fx);
            }
        }
    }

    anss = top;
    top = n*m+1;
    for(int i = q;i >= 1;i--)
    {
        ans[i] = anss;
        shan(i);
    }
    for(int i = 1;i <= q;i++)
    {
        printf("%d\n",ans[i]);
    }
    return 0;
}