Artwork 18年中南多校第一场A

一、题意

对于一个矩阵，若干道命令，每道命令将会把某一段格子涂黑，请问每次涂黑之后矩阵中未被涂黑的块的数量？

二、思路

保存每道命令，并且忠实的执行他，到最后一步开始搜索联通块的数量，并将其保存。

之后对于每道命令做撤回操作。每次撤回之后重新扫描命令覆盖区域中已经是空白块的区域。并且将它们用并查集的方式统一起来。

最后倒序输出保存的答案。

三、代码实现

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<vector>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<set>
#include<map>
#include<string>
#include<queue>

using namespace std;
#define ll long long 
#define veci vector<int>
#define pp pair<ll,ll>
#define vecp vector<pp>

const ll MAXN=1233;

class point
{
    public :
        int x;int y;
        point(){}
        point(int a,int b):x(a),y(b){}
        bool const operator == (point const &p1)
        {
            return x==p1.x&&y==p1.y;
        }
};

class order
{
    public :
        point from,to;
        order(){}
        order(int a,int b,int c,int d)
        {
            from = point(a,b);
            to = point(c,d);
        }
};
ll n,m,k,num;
vector<order>ord;
veci ans;
point sett[MAXN][MAXN];
int mapp[MAXN][MAXN];
int addx[]={0,0,1,-1};
int addy[]={1,-1,0,0};

void draw(order o1)
{
    for(int i=o1.from.x;i<=o1.to.x;++i)
    {
        for(int j=o1.from.y;j<=o1.to.y;++j)
        {
            if(mapp[i][j]==-1)mapp[i][j]=0;
            mapp[i][j]++;    
        }        
    }
}
void erase(order o1)
{
    for(int i=o1.from.x;i<=o1.to.x;++i)
    {
        for(int j=o1.from.y;j<=o1.to.y;++j)
        {
            mapp[i][j]--;    
        }        
    }

}


const point ZERO(0,0);

void dfs(int x,int y,point tar)
{
    if(x<1||x>n||y<1||y>m||mapp[x][y]!=-1||sett[x][y]==tar)return ;        
    sett[x][y]=tar;
    mapp[x][y]=0;
    for(int i=0;i<4;++i)
    {
        dfs(x+addx[i],y+addy[i],tar);    
    }
}    

point find_set(int x,int y)
{
    if(sett[x][y].x==x&&sett[x][y].y==y)return sett[x][y];
    else return sett[x][y]=find_set(sett[x][y].x,sett[x][y].y);
}

void show(point p1)
{
    int x=p1.x;
    int y=p1.y;
    cout<<"x: "<<x<<" y: "<<y<<endl;
}

void deal(order o1)
{
    for(int i=o1.from.x;i<=o1.to.x;++i)
        for(int j=o1.from.y;j<=o1.to.y;++j)
        {
            if(mapp[i][j]==0)
            {
                int isDealed=0;
                for(int k=0;k<4;++k)
                {
                    int x=i+addx[k];
                    int y=j+addy[k];
                    if(x<1||y<1||x>n||y>m)continue;
                    if(mapp[x][y]==0)
                    {
                        if(sett[x][y]==ZERO)continue;
                        if(!isDealed)
                        {            
                            sett[i][j]=sett[x][y]=find_set(x,y);    
                                                                            
                        }else
                        {
                            
                            sett[x][y]=find_set(x,y);
                            sett[i][j]=find_set(i,j);
                            if(sett[i][j]==sett[x][y])continue;                    
                            int xx=sett[x][y].x;
                            int yy=sett[x][y].y;
                            sett[xx][yy]=sett[i][j];
                            num--;
                        }
                        isDealed++;
                    }
                }if(!isDealed)
                {
                    sett[i][j]=point(i,j);
                    num++;    
                }
                
            }
        }
                
}

void init()
{
    num=0;
    ord.clear();
    ans.clear();
    memset(mapp,-1,sizeof(mapp));
    memset(sett,0,sizeof(sett));
    for(int i=0;i<k;++i)
    {
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        order o1(a,b,c,d);
        draw(o1);
        ord.push_back(o1);
    }    
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
        {
            if(mapp[i][j]==-1)
            {
                point tar(i,j);
                dfs(i,j,tar);
                num++;    
            }
        }
    ans.push_back(num);
    
    int len=ord.size();
    for(int i=len-1;i;--i)
    {
            order now=ord[i];
            erase(now);
            deal(now);
            ans.push_back(num);
    }
    len = ans.size();
    for(int i=len-1;i>=0;--i)
        cout<<ans[i]<<endl;
    
        

}


int main()
{
//    cin.sync_with_stdio(false);    
    
    while(cin>>n>>m>>k)init();

    return 0;
}