<= 求赞qwq,码字不易,你的支持是我写作的动力
宣传一下算法提高课题解合集
1250.格子游戏
$Alice$ 和 $Bob$ 玩了一个古老的游戏:首先画一个 $n \times n$ 的点阵(下图 $n = 3$ )。
接着,他们两个轮流在相邻的点之间画上红边和蓝边:
直到围成一个封闭的圈(面积不必为 $1$)为止,“封圈”的那个人就是赢家。因为棋盘实在是太大了,他们的游戏实在是太长了!
他们甚至在游戏中都不知道谁赢得了游戏。
于是请你写一个程序,帮助他们计算他们是否结束了游戏?
输入格式
输入数据第一行为两个整数 $n$ 和 $m$。$n$表示点阵的大小,$m$ 表示一共画了 $m$ 条线
以后 $m$ 行,每行首先有两个数字 $(x, y)$,代表了画线的起点坐标
接着用空格隔开一个字符,假如字符是 $D$,则是向下连一条边,如果是 $R$ 就是向右连一条边
输入数据不会有重复的边且保证正确
输出格式
输出一行:在第几步的时候结束
假如 $m$ 步之后也没有结束,则输出一行“$draw$”
数据范围
$1 \le n \le 200$
$1 \le m \le 24000$
观察题意:发现我们要判断画完线后有没有围成环
而如果能围成一个环,那么最后画的线的两个端点必然已经在一个连通块内
判断是否在一个连通块————使用并查集
并查集是一种树型的数据结构,用于处理一些不相交集合($disjoint sets$)的合并及查询问题
算法步骤如下:
- 如果两个端点已经在同一个集合(
find
操作),那么成环 - 如果两个端点不在同一个集合内(
find
操作),那么这两个集合连通,合并两个集合(merge
操作)
实现小细节
注意到这个地图是二维的,而存点时下表是一维的
所以存点时,我们让点 f[i][j]
对应下标 n * i + j
c++ 代码
#include <bits/stdc++.h>
using namespace std;
//做题时的记录
//算法:并查集
//思路:如果成"圈",那么必定有一个环
// -> 可以用树来存联通的点
// -> 合并过程像merge -> 并查集
//复杂度:约O((n ^ 2) log (n ^ 2))
//实现细节:二维转一维 -> (i, j) <=> i * n + j
typedef long long ll;
const int N = 40009;
int n, m, p[N];
int find(int x)
{
if(x == p[x]) return x;
else return p[x] = find(p[x]);
}
void merge(int x, int y)
{
p[find(x)] = find(y);
}
int main() {
cin >> n >> m;
for(int i = 1;i <= n * n;++ i) p[i] = i;//初始化放cin后~~
char c;
for(int i = 1, a, b;i <= m;++ i)
{
cin >> a >> b >> c;//注意这不是输入的点的坐标
int x = (a - 1) * n + b, y;//点的坐标
if(c == 'D') y = a * n + b;//向下连边
else y = (a - 1) * n + b + 1;//向右连边
if(find(x) == find(y))//如果在同一格子内
{
cout << i << endl;
return 0;
}
merge(x, y);//合并两个集合
}
cout << "draw" << endl;
return 0;
}
大佬,点坐标映射,为啥是(a - 1) * n + b,而不是a * n + b
它x,y都从1开始的
可以不减,唯一就好,如果不减,就注意开的p[N]的空间要多n
所以才要减一。。。。。
我们枚举到的点的下标假设为t,新走到的点的坐标假设为idx
当我们需要这两个点不在同一集合的时候,我们需要合并集合
那么p[find(idx)] = find(t)是可以的
但是为什么p[idx] = find(t)不对呢?卡最后一个点
需要合并的时候,idx肯定不在原来的集合中,为什么不能直接让它的父节点等于原来集合的根结点find(t)呢?