---

独有病眼花，春风吹不落。 (二维坐标压缩成一个点，并查集)

原创 于 2024-05-07 21:25:08 发布 · 粉丝可见 · 818 阅读 · 8 · 4 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/138545935

本题链接： 登录—专业IT笔试面试备考平台_牛客网

题目：

样例：

cobol<br/>3 8<br/>1 1 D<br/>1 1 R<br/>1 2 D<br/>2 1 D<br/>2 2 R<br/>3 1 R<br/>3 2 R<br/>2 3 D<br/>

8

思路：

根据题意，要求连接线段后，操作多少次，连接的线段闭合，如果操作完都没有闭合，说明平局输出“draw”。

在这里，我们可以将线段当作拥有两个点，当我们所画的线段两端的点是头和尾的时候，说明我们画闭合了。所以根据寻找当前点的根结点的时候就是头结点。我们很容易联想到并查集。

这里有个难题就是如何将二维坐标化成一个点的形式存在。我们可以通过映射的方式，由于坐标的 x,y是唯一坐标，所以我们可以结合 x 和 y的结合唯一特点性，转化为一个点映射在我们范围之外即可。

二维坐标化为一个点函数：

inline int getPost(int x,int y)
{
    return x*n + y;
}

随后就是模板并查集的合并查询操作即可。

代码详解如下：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#define endl '\n'
#define x first
#define y second
#define int long long
#define YES puts("YES")
#define NO puts("NO")
#define umap unordered_map
#define All(x) x.begin(),x.end()
#pragma GCC optimize(3,"Ofast","inline")
#define IOS std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e7 + 10;
inline void solve();

signed main()
{
//	freopen("a.txt", "r", stdin);
	IOS;
	int _t = 1;
	// cin >> _t;
	while (_t--)
	{
		solve();
	}
	return 0;
}
int n,m;
int f[N];

// 二维坐标转化一维点
inline int getPost(int x,int y)
{
	return x*n + y;
}
inline void Init()
{
	for(int i = 1;i <= n * n;++i) f[i] = i;
}
inline int Finds(int x)
{
	int t = x;
	while(f[x] != x) x = f[x];
	f[t] = x;
	return x;
}
inline void solve()
{
	cin >> n >> m;
	Init();	// 并查集初始化操作
	for(int step = 1;step <= m;++step)
	{
		int x,y;
		char op;
		cin >> x >> y >> op;
		--x,--y;	// 小优化，省一省空间
		int b,a = getPost(x,y);	// 二维坐标转化一维点
		if(op == 'D') b = getPost(x + 1,y);
		else b = getPost(x,y + 1);
		a = Finds(a),b = Finds(b);	// 查找线段两端的根节点
		if(a == b)	// 如果两端的根节点一致，说明出现了闭区间
		{
			cout << step << endl;
			return ;
		}
		f[a] = b;	// 合并区间
	}
	cout << "draw" << endl;
}

最后提交：