AcWing 1250. 格子游戏
原题链接
简单
作者:
冷丁Hacker
,
2020-11-04 20:02:43
,
所有人可见
,
阅读 418
单链并查集
#include<bits/stdc++.h>
using namespace std;
const int N = 40010;
int p[N];
int n, m;
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;
int x, y;
char c;
int num;
int ok = 0;
for (int i = 0; i < n * n; i++) {
p[i] = i;
}
for (int i = 1; i <= m; i++) {
cin >> x >> y >> c;
x--; y--;
if (c == 'D') {
num = get(x+1, y);
}
else {
num = get(x, y+1);
}
int num1 = get(x, y);
int pa = find(num);
int pb = find(num1);
if (pa == pb) {
ok = i;
break;
}
p[pa] = p[pb];
}
if (!ok) {
cout << "draw" << endl;
}
else cout << ok << endl;
return 0;
}