AcWing 1250. 格子游戏（并查集，坐标变换）

本文主要是介绍AcWing 1250. 格子游戏（并查集，坐标变换），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

记录此题的目的：

明确二维的坐标可以映射到一维：在x和y都是从0开始的前提下，假如图形列数为n，(x,y)映射到一维可以写成x * n + y。
并查集并不好存储二维数据，如果遇到二维数据可以将其映射到一维。

Alice和Bob玩了一个古老的游戏：首先画一个 $n \times n$ 的点阵（下图 $n = 3$ ）。

接着，他们两个轮流在相邻的点之间画上红边和蓝边：

在这里插入图片描述

直到围成一个封闭的圈（面积不必为 $1$ ）为止，“封圈”的那个人就是赢家。因为棋盘实在是太大了，他们的游戏实在是太长了！

他们甚至在游戏中都不知道谁赢得了游戏。

于是请你写一个程序，帮助他们计算他们是否结束了游戏？

输入格式
输入数据第一行为两个整数 $n$ 和 $m$ 。 $n$ 表示点阵的大小， $m$ 表示一共画了 $m$ 条线。

以后 m 行，每行首先有两个数字 $(x, y)$ ，代表了画线的起点坐标，接着用空格隔开一个字符，假如字符是 D，则是向下连一条边，如果是 R就是向右连一条边。

输入数据不会有重复的边且保证正确。

输出格式
输出一行：在第几步的时候结束。

假如 $m$ 步之后也没有结束，则输出一行draw。

数据范围
$1 \leq n \leq 200 ，$
$1 \leq m \leq 24000$

输入样例：

输出样例：

一道并查集的裸题。
首先游戏的结束是指有任何一部分连成了环，而连成环的条件就是有一个点连上了和它连通的点，也就是他们两个在同一个集合里。

主要难点，考察点是如果记录数据，这里采用将二维坐标映射到一维的做法。
使用公式： $x * (列数) + y$

代码：

#include<iostream>
using namespace std;
const int N = 210;int p[N * N];
int n, m;int find(int x) {if (p[x] != x)p[x] = find(p[x]);return p[x];
}int main() {cin >> n >> m;for (int i = 0; i <= n * n+1; i++)p[i] = i;int ans = 0;bool has_answer = 0;for(int i = 1;i <= m;i++) {int x, y; cin >> x >> y;x--,y--;int a = x * n + y;  //映射到一维char op; cin >> op;int b;if(op == 'D')b = (x+1)*n + y;else b = x * n + y + 1;if(find(a) == find(b)){has_answer = 1;ans = i;break;}else{p[find(a)] = find(b);}}if (has_answer)cout << ans;else cout << "draw";return 0;
}