思路
这题基本思路就是建图判环,但是我们发现可以用裸并查集来做。
-
网格点:图中的点
-
网格边:图中的边
初始化状态下,每个点都是自己孤立的一个集合,每增加一条边,相当于合并了两个集合。
所以如果不出现环,那么新增的这条边的终点和这条边的起点在画边之前必不属于同一个集合,否则就会形成一个环。每增加一条边,就会将两个集合的点合并起来。
由于并查集初始化是一维的,所以我们可以二维左边变成一维坐标来做,见get()
函数。
代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 40010;
int n, m;
int p[N];
int get(int x, int y)
{
x--, y--;
return x * n + y;
}
int find(int x)
{
if (p[x] == x) return x;
else return p[x] = find(p[x]);
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n * n; i++) p[i] = i;
int res = 0;
for (int i = 1; i <= m; i++)
{
int x, y;
char c;
cin >> x >> y >> c;
int a = get(x, y);
int b;
if (c == 'D') b = get(x + 1, y);
else b = get(x, y + 1);
int fa = find(a), fb = find(b);
if (fa == fb)
{
res = i;
break;
}
p[fa] = fb;
}
if (res != 0) cout << res;
else cout << "draw";
return 0;
}