格子游戏

并查集 T2 信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)

题目描述

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

接着，他们两个轮流在相邻的点之间画上红边和蓝边：

直到围成一个封闭的圈（面积不必为1）为止，“封圈”的那个人就是赢家。因为棋盘实在是太大了(n ≤ 200)，他们的游戏实在是太长了！他们甚至在游戏中都不知道谁赢得了游戏。于是请你写一个程序，帮助他们计算他们是否结束了游戏？

输入

输入数据第一行为两个整数n和m。m表示一共画了m条线。以后m行，每行首先有两个数字(x, y)，代表了画线的起点坐标，接着用空格隔开一个字符，假如字符是”D “，则是向下连一条边，如果是”R “就是向右连一条边。输入数据不会有重复的边且保证正确。

输出

输出一行：在第几步的时候结束。假如m步之后也没有结束，则输出一行“draw”。

输入样例

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

输出样例

4

思路

能够封圈的最后一条边所连接的两个点a b, 这两个点一定已经存在一条路径使其连通, 也就是在一个集合内。

故只需要判断边的两端点是否在一个集合内即可。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
#define x first
#define y second
const int N = 220;
typedef pair<int, int> PII;
PII point[N][N];
PII f[N][N];
 
PII find(PII x)
{
    if (x != f[x.x][x.y])
        f[x.x][x.y] = find(f[x.x][x.y]);
    return f[x.x][x.y];
}
 
void merge(PII a, PII b)
{
    f[a.x][a.y] = f[b.x][b.y];
}
 
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= n; j++)
            f[i][j] = {i, j};
 
    bool flag = false;
    int res = 0;
    for (int i = 1; i <= m; i++)
    {
        int a, b, x, y;
        char s[2];
        cin >> a >> b >> s;
        if (s[0] == 'D')
            x = a + 1, y = b;
        else
            x = a, y = b + 1;
 
        PII pa = find({a, b}), pb = find({x, y});
        if (pa != pb)
            merge(pa, pb);
        else if (!flag)
        {
            flag = true;
            res = i;
        }
    }
    if (flag)
        cout << res << endl;
    else
        cout << "draw\n";
 
    return 0;
}