[数据结构与算法]数据结构--格子游戏

题目描述

Alice和Bob玩了一个古老的游戏：首先画一个 $n\times n$ 的点阵（下图 $n$ = 3 ）。

接着，他们两个轮流在相邻的点之间画上红边和蓝边：
https://cdn.acwing.com/media/article/image/2019/12/11/19_9edbcf521b-1.png
直到围成一个封闭的圈（面积不必为 1）为止，“封圈”的那个人就是赢家。因为棋盘实在是太大了，他们的游戏实在是太长了！

他们甚至在游戏中都不知道谁赢得了游戏。

于是请你写一个程序，帮助他们计算他们是否结束了游戏？

输入格式

输入数据第一行为两个整数 $n$ 和 $m$。$n$ 表示点阵的大小，$m$ 表示一共画了 $m$ 条线。

以后 $m$ 行，每行首先有两个数字 $(x,y)$，代表了画线的起点坐标，接着用空格隔开一个字符，假如字符是 $D$，则是向下连一条边，如果是 $R$ 就是向右连一条边。

输入数据不会有重复的边且保证正确。

输出格式

输出一行：在第几步的时候结束。

假如 $m$ 步之后也没有结束，则输出一行“draw”。

数据范围

$1\le n\le 200$ ，
$1\le m\le 24000$

样例

输入样例

3 5
1 1 D
1 1 R
1 2 D
2 1 R
2 2 D

输出样例

4

样例解释

第一步：(1, 1)向(2,1)连一条边; 第二步：(1, 1)向(1,2)连一条边; 
第三步：(1, 2)向(2,2)连一条边; 第四步：(2, 1)向(2,2)连一条边; 
成环、在第四步的时候结束！！！

思路 (并查集)

本题考察的是并查集的基本用法，上述问题可以转换为：每个点都是一个单独的集合，如果没有构成一个环，就可以在两个集合之间连一条边，如果在一个集合中，那么就代表这两个集合会成环。

1. 将每个坐标看成一个点值，为了方便计算，将所有的坐标横纵坐标都减1，第一个位置即(1,1)看成是0，(1,2)看成是1，依次类推，将所有的坐标横纵坐标都减1后，假设当前点是(x,y)，该点的映射值是a = (x * n + y)，若向下画，则b = [(x + 1) * n + y],若向右画，则b = [x * n + y - 1]。

2. 枚举所有操作，通过并查集操作判断a和b是否在同一个集合：
   • 若在同一个集合则标记此操作可以让格子形成环
   • 若不在同一个集合，则需要将两个集合进行合并
     

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 40010;

int n, m;
int p[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];
}

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;
        char d;
        cin >> x >> y >> d;
        x --, y --;
        
        // 二维的转换成一维的
        int a = get(x, y);
        int b;
        if (d == 'D') b = get(x + 1, y);
        else b = get(x, y + 1);
        
        // 判断是不是在一个集合中！
        int pa = find(a), pb = find(b);
        if (pa == pb)
        {
            res = i;
            break;
        }
        
        p[pa] = pb;
    }
    
    if (!res) puts("draw");
    else cout << res << endl;
    
    return 0;
}