1250. 格子游戏

Solost

2023 年 01 月 24 日

241 次浏览

暂无评论

1085字数

题目题解

![](https://amarantos.oss-cn-hangzhou.aliyuncs.com/typecho/2023/01/1909121154.png)

## 题目大意

题目大概意思是每次可以从x, y到x+1,y或者x,y+1,如果出现环就输出第几回合出现环的，否则就输出draw。

## solution

这道题就是判断出现环的问题，我们假设，当前点是x,y，下一个连接的点,如果两个点的父亲一样，那么就可以确定现在已经出现了环。

### 并查集写法

```cpp
int find(int x)
{
    if(x != p[x]) p[x] = find(p[x);
    return p[x];
}

```

### 二维数组压缩为一维

由于并查集查找父亲是一个一位坐标，需要把二维数组压缩成为一个维度来表示他的父亲。

当坐标从(0,0)开始的时候，我们可以将d = x * n + y,n就是行数，所以我们就可以这样来表示。

```CPP
#include <bits/stdc++.h>

using namespace std;
int n, m;
const int N = 4010; /二维压缩过来最多的点的个数
int p[N];
int find(int x){
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int get(int x, int y){
    return x * n + y;
}
int main(){
    cin >> n >> m;
    for(int i = 0; i <= n * n; i++) p[i] = i;
    int res = 0;
    for(int i = 1; i <= m; i++){
        int x, y, a, b;
        char op;
        cin >> x >> y >> op;
        x--, y--;
        a = get(x, y);
        if(op == 'D') b = get(x + 1, y);
        else b = get(x, y + 1);
        int fa = find(a);
        int fb = find(b);
        if(fa != fb) p[fb] = fa;
        else{
            res = i;
            break;
        }
    }
    if(!res) puts("draw");
    else cout << res << endl;
    return 0;
}
```

最后修改：2023 年 02 月 02 日