AcWing 1250. 格子游戏
原题链接
简单
作者:
松鼠爱葡萄
,
2020-10-17 10:05:03
,
所有人可见
,
阅读 706
#include<iostream>
#include<cstring>
using namespace std;
const int N = 4e4 + 10;
int n, m;
int p[N];
int get(int x, int y) {
return x * n + y;
}
int find(int x) {
if (x != p[x]) p[x] = find(p[x]);
return p[x];
}
int main() {
cin >> n >> m;
for (int i = 1; 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 = 0;
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;
} else {
p[pb] = pa;
}
}
if (res) cout << res << endl;
else puts("draw");
}