信息学奥赛一本通 1347：【例4-8】格子游戏

【题目链接】

ybt 1347：【例4-8】格子游戏

【题目考点】

1. 并查集：判断无向图是否有环

【解题思路】

该题为判断无向图是否有环。可以使用并查集来完成。

学习并查集时，每个元素都由一个整数来表示。而该问题中每个元素是一个坐标点，由(x, y)两个整数构成。
因而有两种方法解决该问题

解法1：将二维坐标变为一个整数

通过一个公式将二维坐标换算为一个整数，用这个整数代表该二维坐标。

例：假设坐标点是2行3列的，每个位置的坐标为x, y，转变后的数字为d，记为(x, y):d

	第1列	第2列	第3列
第1行	(1,1):1	(1,2):2	(1,3):3
第2行	(2,1):4	(2,2):5	(2,3):6

可以推出n行n列的坐标系中，坐标(x,y)转为数字d，公式为：$d=(x-1)\cdot n+y$
把每个坐标都用一个数字表示。
每输入一个坐标(x,y)，求出其对应的数字f。

• 如果接下来输入字母D，即向下画，那么与(x,y)连接的点是(x+1, y)，求出其对应的数字t。
• 如果接下来输入字母R，即向右画，那么与(x,y)连接的点是(x, y+1)，求出其对应的数字t。

判断f和t是否在一个集合（连通子图）中

• 如果是，那么f与t连边会形成环，游戏结束。输出游戏结束时的步数。
• 否则把f和t所在的集合合并。

解法2：直接使用坐标作为并查集中的元素

如果并查集中的元素不为整数，可以将fa数组改为映射（map类型），同时find、merge都发生改变。
解题思路与解法1类似。
在输入时，使用find直接判断两个数对元素是否在一个集合中

• 如果已在一个集合中，说明两点间有路径连通，再加一条边就会形成环。
• 否则，使用merge把两个数对元素所在的集合进行合并。

【题解代码】

解法1：将二维坐标变为一个整数

#include<bits/stdc++.h>
using namespace std;
#define N 40005
int fa[N], n, m;
int getNum(int x, int y)//用1个数字代表二维的坐标点 
{return (x-1)*n + y;
}
void init(int n)
{for(int i = 1; i <= n; ++i)fa[i] = i;
}
int find(int x)
{if(x == fa[x])return x;elsereturn fa[x] = find(fa[x]);
}
void merge(int x, int y)
{ fa[find(x)] = find(y);
}
int main()
{int x, y, i, f, t;char c;cin >> n >> m;init(n*n);for(i = 1; i <= m; ++i)//i：第几步 {cin >> x >> y >> c;f = getNum(x, y);if(c == 'D')t = getNum(x+1, y);else//c == 'R't = getNum(x, y+1);if(find(f) == find(t))break;elsemerge(f, t);}if(i <= m)cout << i;elsecout << "draw";return 0;
}

解法2：直接使用坐标作为并查集中的元素

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> Pair;
map<Pair, Pair> fa;
Pair find(Pair x)
{if(x == fa[x])return x;elsereturn fa[x] = find(fa[x]);
}
void merge(Pair x, Pair y)
{fa[find(x)] = find(y);
}
int main()
{Pair p, q;int n, m, x, y;char c;cin >> n >> m;for(int i = 1; i <= m; ++i){cin >> x >> y >> c;p = Pair(x, y);if(c == 'D')q = Pair(x+1, y);else//c == 'R'q = Pair(x, y+1);if(fa.count(p) == 0)//如果不存在该点，则初始化 fa[p] = p;if(fa.count(q) == 0)fa[q] = q;if(find(p) == find(q))//p, q已连通，p，q再连边，则存在环 {cout << i;//输出步数 return 0;}merge(p, q);//合并两点 }cout << "draw";return 0;
}