本文主要是介绍并查集求解百练2790:迷宫，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
并查集(union-find sets)求解：百练 2790 迷宫
http://bailian.openjudge.cn/practice/2790
描述
一天Extense在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由n * n的格点组成，每个格点只有2种状态，.和#，前者表示可以通行后者表示不能通行。同时当Extense处在某个格点时，他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Extense想要从点A走到点B，问在不走出迷宫的情况下能不能办到。如果起点或者终点有一个不能通行(为#)，则看成无法办到。
输入
第1行是测试数据的组数k，后面跟着k组输入。每组测试数据的第1行是一个正整数n (1 <= n <= 100)，表示迷宫的规模是n * n的。接下来是一个n * n的矩阵，矩阵中的元素为.或者#。再接下来一行是4个整数ha, la, hb, lb，描述A处在第ha行, 第la列，B处在第hb行, 第lb列。注意到ha, la, hb, lb全部是从0开始计数的。
输出
k行，每行输出对应一个输入。能办到则输出“YES”，否则输出“NO”。
样例输入
2
3
.##
..#
#..
0 0 2 2
5
.....
###.#
..#..
###..
...#.
0 0 4 0
样例输出
YES
NO
思路
- 用一组数组表示迷宫
- 根结点相同，则两点连通
源码
#include <iostream>
using namespace std;const int MAXN = 100;
char maze[MAXN*MAXN];
int fa[MAXN*MAXN];int find_root(int x) {int r = x;while (fa[r] != r)r = fa[r];while (x != r) {int t = x;x = fa[x];fa[t] = r;}return r;
}void join(int a, int b) {int roota = find_root(a);int rootb = find_root(b);if (roota != rootb) {fa[rootb] = fa[roota];}
}void group() {int n;cin >> n;for (int i = 0; i < n * n; i++) {cin >> maze[i];fa[i] = i;}// 第0行for (int i = 1; i < n; i++)if (maze[i] == '.' && maze[i - 1] == '.')join(i - 1, i);// 第0列for (int i = n; i < n * n; i += n)if (maze[i] == '.' && maze[i - n] == '.')join(i - n, i);for (int i = n; i < n * n; i += n)for (int j = 1; j < n; j++)if (maze[i + j] == '.') {if (maze[i + j - n] == '.')join(i + j - n, i + j);if (maze[i + j - 1] == '.')join(i + j - 1, i + j);}int ha, la, hb, lb;cin >> ha >> la >> hb >> lb;cout << (find_root(ha * n + la) == find_root(hb * n + lb)? "YES" : "NO") << endl;
}int main() {//freopen("百练2790迷宫.in.txt", "r", stdin);int k;cin >> k;for (; k > 0; k--)group();return 0;
}
这篇关于并查集求解百练2790:迷宫的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
