[Acwing] 映射坐标 1250. 格子游戏

前言

没想到 第一题 就卡到我了 QAQ (用vector 加 Pair 映射没成功 )

思路

首先 这题 只是要找 是否成环 即可

通过分析 我们 可以发现 当要加的两个点正好在一个集合当中 那么 他们就能构成环

图例如图 (牛逼 反正我没想到 我观察边的规律去了)

所以问题就转换成 并查集 的问题了

• 每次判断 一条边的 起点 和 终点 是否在一个集合当中

那么我们应该怎么判断起点和终点呢 (普通的 find操作 只是对应 一个值 啊喂)

所以我们就需要通过映射的方式了

映射函数 x*n +y 这里解释一下 什么需要 x-- (y可以不用减) 因为对于这个公式 第一行的时候 x相当于是 0 因为 第一行只需要0+y即可 (反正我想了一会才想明白)

CODE

#include 
#define sc(a) scanf("%d",&a)
#define IOS  ios::sync_with_stdio(false)
using namespace std;
const int N = 40010;/// 200 *200 + 10
int n,m,p[N],sz[N];

int get(int x,int y)
{
    return x*n+y ;///相当于坐标映射了
}
int find(int x)
{
    if(p[x]!=x)
        p[x] = find(p[x]);
    return p[x];
}
void solve()
{
    cin>>n>>m;
    for(int i = 0; ix>>y>>op;
        x--;
        int a =get(x,y);
        int b;
        if(op == 'D')
            b=get(x+1,y);
        else
            b=get(x,y+1);

        int pa = find(a);
        int pb = find(b);

        if(pa == pb)
        {
            res  = i;
            break;
        }
       // sz[pa]+=sz[pb];
        p[pa] = pb;
    }

    if(!res)
    puts("draw");
   //     ptn(draw);
    else
        cout