华为OD统一考试 - 欢乐的周末

题目描述

小华和小为是很要好的朋友，他们约定周末一起吃饭。

通过手机交流，他们在地图上选择了多个聚餐地点（由于自然地形等原因，部分聚餐地点不可达），求小华和小为都能到达的聚餐地点有多少个？

输入描述

第一行输入 m 和 n

• m 代表地图的长度
• n 代表地图的宽度

第二行开始具体输入地图信息，地图信息包含：

• 0 为通畅的道路
• 1 为障碍物（且仅1为障碍物）
• 2 为小华或者小为，地图中必定有且仅有2个 （非障碍物）
• 3 为被选中的聚餐地点（非障碍物）

输出描述

可以被两方都到达的聚餐地点数量，行末无空格。

备注

地图的长宽为 m 和 n，其中：

• 4 ≤ m ≤ 100
• 4 ≤ n ≤ 100

聚餐的地点数量为 k，则

• 1< k ≤ 100

用例

题目解析

本题可以使用并查集解题。

小华和小为想去同一个餐厅，那么必然小华和小为和餐厅是可以连通，如果它们不能连通，则去不了同一个餐厅。

因此，我们可以遍历矩阵中每一个元素，将它和其上下左右元素进行连接，需要注意的是如果遍历的元素本身是1，或者其上下左右的元素是1，则不进行连接。

这样的话，遍历完矩阵后，就可以得到一个连通图。

同时在遍历矩阵过程中，记录小华、小为（值为2），以及餐厅（值为3）的位置，遍历结束后，首先看小华和小为是不是同一个祖先，若不是，则二者不可连通，就更别说去同一个餐厅了，因此返回0。若二者可以连通，则再看每一个餐厅的祖先是否和华为的祖先相同，若相同则计数++，这样就可以得到小华，小为去的同一个餐厅的数量了。

本题输入中

• m 代表地图的长度
• n 代表地图的宽度

长度 m 指的是地图矩阵的行数，宽度 n 指的是地图矩阵的列数。

import Foundation

func ODTest_2_42() {
    print("输入描述")
    print("第一行输入 m 和 n, m 代表地图的长度 n 代表地图的宽度")
    let MN = (readLine() ?? "").split(separator: " ").map { Int($0) ?? 0 }
    let M = MN[0], N = MN[1]

    print("第二行开始具体输入地图信息，地图信息包含：")
    // 矩阵
    print("第二行开始，是M行N列的像素的二维数组，仅包含像素1和5")
    var matrix = Array(repeating: Array(repeating: 0, count: N), count: M)
    for i in 0 ..< M {
        matrix[i] = (readLine() ?? "").split(separator: " ").map { Int($0) ?? 0 }
    }
    print("可以被两方都到达的聚餐地点数量，行末无空格。")
    // 记录小华，小为的位置
    var huawei: [Int] = []
    // 记录餐厅的位置
    var restaurants: [Int] = []

    let rows = matrix.count
    let cols = matrix[0].count
    let ufs = UnionFindSet(ro