1347：【例4-8】格子游戏

【题目描述】
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

#include <bits/stdc++.h>
using namespace std ;
typedef long long LL ;
inline LL rd() { register LL x = 0 , f = 1 ; register char c ;
#define gc c = getchar()
    while(isspace(gc)) ;
    if(c == '-') f = -1 , gc ;
    while(x = (x<<1) + (x<<3) + (c&15) , isdigit(gc)) ;
    return x * f ;
#undef gc
}

const int inf = INT_MAX >> 1 ;
int n , m ; 
const int N = 200 + 5 ;
struct node {
    int x , y ;
}fa[N][N] ;
inline node find(node x) {
    return fa[x.x][x.y].x == x.x && fa[x.x][x.y].y == x.y ? x : fa[x.x][x.y] = find(fa[x.x][x.y]) ;
} 
signed main() {
    ios::sync_with_stdio(false) ;
    cin >> n >> m ;
    for(register int i=1;i<=n;i++) 
        for(register int j=1;j<=n;j++) fa[i][j].x = i , fa[i][j].y = j ;
    node xx , yy ;
    for(register int i=1;i<=m;i++) {
        register int x , y ; register char c ;
        cin >> x >> y >> c ;
        if(c == 'D') {
            xx = find(fa[x][y]) ;
            yy = find(fa[x + 1][y]) ;
        }
        if(c == 'R') {
            xx = find(fa[x][y]) ;
            yy = find(fa[x][y + 1]) ;
        }
        if(xx.x == yy.x and xx.y == yy.y) {
            return cout << i << endl , 0 ;
        }
        else fa[xx.x][xx.y] = yy ;
    }
    return puts("draw") , 0 ;
}

1347：【例4-8】格子游戏

原文：https://www.cnblogs.com/qf-breeze/p/10875048.html