作者：风中凌乱2602938623 | 来源：互联网 | 2023-10-14 16:23
题目描述Alice和Bob玩了一个古老的游戏：首先画一个n×n的点阵（下图n3）接着，他们两个轮流在相邻的点之间画上红边和蓝边：直到围成一个封闭的圈（面积不必为1）为止，“封圈”的
题目描述
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
题解
貌似很麻烦，但实际上还是可以直接套并查集。
可以看出，如果点$i$和点$j$连接后形成封闭圈，那么点$i$和点$j$必然都能连通点$k$，我们只需要用并查集判断点$i$和点$j$是否在同一个集合里，就可以知道是否存在这个点$k$了。
#include
#define MAX_N (200 + 5)
using namespace std;
struct Node
{
int x, y;
inline friend bool operator == (Node x, Node y) {return x.x == y.x && x.y == y.y;}
inline friend bool operator != (Node x, Node y) {return !(x == y);}
};
int n, m;
Node r[MAX_N][MAX_N];
Node Root(Node x)
{
Node R = x, tmp;
while(R != r[R.x][R.y]) R = r[R.x][R.y];
while(x != r[x.x][x.y]) tmp = r[x.x][x.y], r[x.x][x.y] = R, x = tmp;
return R;
}
int main()
{
cin >> n >> m;
char ch;
Node u, v;
for(register int i = 1; i <= n; ++i)
{
for(register int j = 1; j <= n; ++j)
{
u = (Node){i, j};
r[i][j] = u;
}
}
for(register int i = 1; i <= m; ++i)
{
cin >> u.x >> u.y >> ch;
v = u;
if(ch == ‘D‘) ++v.x;
else ++v.y;
if(Root(u) == Root(v)) return cout <0;
r[Root(u).x][Root(u).y] = Root(v);
}
cout <<"draw";
return 0;
}
京公网安备 11010802041100号