格子游戏——并查集+二维坐标映射成一维方法_二维到一维的映射不是单射

引入

假设给我们一个$n\ast m$的矩形，里面依次填入坐标，从$(1,1)$开始；

映射方式其实就是将这些坐标依次填入一个$n\ast m$的一维数组；

解释

公式为$(x-1)\ast m+y$

其中$(x-1)\ast m$表示在当前数之前已经有几个数；

而$+y$则代表自己是第几个数；

比如上图中的$(2,1)$代入公式，前面有$m$个数，自己是第1个数；因此映射到第$m+1$位；

例题

具体见代码中的$get(x,y)$函数

Code

#include <iostream>

using namespace std;

const int N = 4e4+10;

int p[N];

int _find(int x){
    if(p[x] == x) return x;
    return _find(p[x]);
}
int n,m;
int get(int x,int y){
    return (x-1)*n+y;
}
int main(){
    cin >> n >> m;
    for(int i=1;i<=n*n;++i) p[i] = i;
    int x,y;
    char d;
    int ans = -1;
    for(int i=1;i<=m;++i){
        cin >> x >> y >> d;
        int xx = get(x,y),yy;
        if(d == 'D'){
            yy = get(x+1,y);
        }else{
            yy = get(x,y+1);
        }
        int pxx = _find(xx);
        int pyy = _find(yy);
        if(pxx == pyy){
            ans = i;
            break;
        }
        p[pxx] = pyy;
    }
    if(ans == -1) cout << "draw\n";
    else cout << ans << '\n';
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

补充说明

如果坐标从$(0,0)$开始

那么公式为$x\ast m+y$