AcWing 1250. 格子游戏 (并查集,坐标变换)

时间:2024-03-23 19:50:40

记录此题的目的:

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

Alice和Bob玩了一个古老的游戏:首先画一个 n × n n×n n×n 的点阵(下图 n = 3 n=3 n=3 )。

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

在这里插入图片描述

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

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

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

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

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

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

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

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

数据范围
1 ≤ n ≤ 200 , 1≤n≤200, 1n200
1 ≤ m ≤ 24000 1≤m≤24000 1m24000

输入样例:

3 5
1 1 D
1 1 R
1 2 D
2 1 R
2 2 D

输出样例:

4

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

主要难点,考察点是如果记录数据,这里采用将二维坐标映射到一维的做法。
使用公式: x ∗ ( 列数 ) + y x * (列数) + y 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;
}