杭电5652 India and China Origins（并查集求是否连通）

- 日理万妓 2022-07-25 19:29 50阅读 0赞

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=5652][http_acm.hdu.edu.cn_showproblem.php_pid_5652]

题目大意：给你一个用n\*m个小方块组成的长方形矩阵，其中有一些小方块不能经过，左下角坐标为(0,0)，给你Q组坐标，每组坐标会把可以经过的小方块变成不能经过的小方块，问从第几组坐标开始矩阵的上部就不能到达矩阵的下部，如果都能到达输出-1。

解题思路：（第一次知道这种题还能用并查集做），我们可以倒着想，先将Q组坐标对应的小方块变成不能经过的，然后一个一个去掉，判断去掉哪个点可以连通即可。

具体操作就是先将首先将Q组坐标对应的小方块变成不能经过的，建立两个结点，第一个结点与第一排能经过的结点合并为一个集合，第二个结点与最后一排能经过的结点合并为一个集合，然后遍历矩阵将能联通结点连通，最后判断，两个节点是否在一个集合，如果不在，就按照坐标把小方块变成可以经过，再将合并小方块周围的四个小方块合并到一个集合里，再判断两个结点是否在一个集合，如此循环即可。

#include <vector>
    #include <list>
    #include <map>
    #include <set>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <bitset>
    #include <algorithm>
    #include <functional>
    #include <numeric>
    #include <utility>
    #include <sstream>
    #include <iostream>
    #include <iomanip>
    #include <cstdio>
    #include <cmath>
    #include <cstdlib>
    #include <cstring>
    #include <ctime>
    #include <cassert>
    #define RI(N) scanf("%d",&(N))
    #define RII(N,M) scanf("%d %d",&(N),&(M))
    #define RIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
    #define mem(a) memset((a),0,sizeof(a))
    using namespace std;
    const int inf=1e9;
    const int inf1=-1*1e9;
    typedef long long LL;
    char ma[505][505];
    int ima[505][505];
    int par[250005];
    int rankk[250005];
    int xx[4]= {
       1,0,-1,0};
    int yy[4]= {
       0,1,0,-1};
    vector< pair<int,int> > qq;
    void init(int n)
    {
        for(int i=0; i<n; i++)
        {
            par[i]=i;
            rankk[i]=0;
        }
    }
    int findd(int x)
    {
        if(par[x]==x) return x;
        else return par[x]=findd(par[x]);
    }
    
    void unite(int x,int y)
    {
        x=findd(x);
        y=findd(y);
        if(rankk[x]<rankk[y]) par[x]=y;
        else
        {
            par[y]=x;
            if(rankk[x]==rankk[y]) rankk[x]++;
        }
    }
    int main()
    {
        int t;
        RI(t);
        while(t--)
        {
            mem(ima);
            int n,m,Q;
            RII(n,m);
            for(int i=0; i<n; i++)
                scanf("%s",ma[i]);
            for(int i=0; i<n; i++)
                for(int j=0; j<m; j++)
                    ima[i][j]=ma[i][j]-'0';
            RI(Q);
            int ans=Q;
            while(Q--)
            {
                int x1,y1;
                RII(x1,y1);
                ima[x1][y1]=1;
                pair<int,int>ppp(x1,y1);
                qq.push_back(ppp);
            }
    
            init(n*m+5);
            for(int i=0; i<m; i++)
            {
                if(ima[0][i]==0) unite(0,i+1);
            }
    
            for(int i=1; i<n; i++)
                for(int j=0; j<m; j++)
                {
                    if(ima[i][j]==0)
                    {
                        if(i-1>=0&&ima[i-1][j]!=1)
                        {
                            unite(i*m+j+1,(i-1)*m+j+1);
                        }
                        if(j-1>=0&&ima[i][j-1]!=1)
                        {
                            unite(i*m+j+1,i*m+j-1+1);
                        }
                    }
                }
    
    
            for(int i=0; i<m; i++)
            {
                if(ima[n-1][i]==0) unite(m*n+1,(n-1)*m+i+1);
            }
    
            if(findd(0)==findd(m*n+1))
                cout<<-1<<endl;
            else
            {
                for(int i=ans-1; i>=0; i--)
                {
                    int x=qq[i].first;
                    int y=qq[i].second;
                    ima[x][y]=0;
                    for(int j=0; j<4; j++)
                    {
                        int x2=x+xx[j];
                        int y2=y+yy[j];
                        if(x2>=0&&x2<n&&y2>=0&&y2<m&&ima[x2][y2]==0)
                        {
    
                            unite(x2*m+y2+1,x*m+y+1);
                        }
                        else if(x2==-1)
                        {
                            unite(y2+1,0);
                        }
                        else if(x2==n)
                        {
                            unite(n*m+1,(n-1)*m+y2+1);
                        }
                    }
                    ans--;
                    if(findd(0)==findd(m*n+1)) break;
    
    
                }
                cout<<ans+1<<endl;
            }
            qq.clear();
        }
        return  0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_5652]: http://acm.hdu.edu.cn/showproblem.php?pid=5652