蓝桥集训之格子游戏

蓝桥集训之格子游戏

• 核心思想：并查集

  • 将二维坐标转化为一维坐标 x*n+y
  • 每次将两个点合并 同时判断两点是否在同一集合内
  • 若在 则本次连接可以成环

•   #include<iostream>
    #include<cstring>
    
    using namespace std;
    const int N = 40010;  //原本的n 的平方
    
    int p[N];
    int n,m;
    
    int getxy(int x,int y)
    {
        return x*n + y;  //转化一维坐标
    }
    
    int find(int x)
    {
        if(p[x]!=x) p[x] = find(p[x]);
        return p[x];
    }
    
    int main()
    {
        cin>>n>>m;
        for(int i=0;i<n*n;i++) p[i] = i;  //最大n * n
        
        int res=0;
        for(int i=1;i<=m;i++)
        {
            int x,y;
            char d;
            cin>>x>>y>>d;
            x -- , y --;  //坐标从0开始才可以转化
            int a = getxy(x,y);
            int b;
            if(d == 'D') b = getxy(x+1,y);  //往下走 找下点的坐标
            else b = getxy(x,y+1);  //找右点的坐标
            
            int pa = find(a) , pb = find(b);
            if(pa == pb)  //本次成环
            {
                res = i;
                break;
            }
            else
            {
                p[pa] = pb;
            }
        }
        if(res == 0) puts("draw");
        else cout<<res;
    }