格子游戏

格子游戏

实现

#include <cstdio>
using namespace std;

const int N = 40010;
int n, m;
int f[N];

int find (int x) {
    if (f[x] == x) return x;
    return f[x] = find(f[x]);
}
void merge (int x, int y) {
    f[find(x)] = find(y);
}
bool query (int x, int y) {
    return find(x) == find(y);
}
int index_of (int i, int j) {
    return i * (n - 1) + j;
}

int main () {
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n * n; ++ i) f[i] = i;
    int res = 0;
    for (int i = 1, x, y; i <= m; ++ i) {
        char opt[5];
        scanf("%d%d%s", &x, &y, opt);

        int a = index_of(x, y),
            b = (opt[0] == 'D' ? index_of(x + 1, y) : index_of(x, y + 1));
        if (query(a, b) == false) {
            merge(a, b);
        } else {
            res = i;
            break;
        }
    }
    if (res == 0) {
        printf("draw");
    } else {
        printf("%d", res);
    }
    return 0;
}