华为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(rows * cols)
    getResult()
    
    // 小华所在连通分量的根
    let hua_fa = ufs.find(huawei[0])
    // 小为所在连通分量的根
    let wei_fa = ufs.find(huawei[1])
    // 如果小华和小为的不属于同一个连通分量，则二人无法去往相同餐厅
    if hua_fa != wei_fa {
        print("0")
        return
    }
    // 找出和小华、小为在同一个连通分量里面的餐厅
    var ans = 0
    for restaurant in restaurants {
        if ufs.find(restaurant) == hua_fa {
            ans += 1
        }
    }
    print("\(ans)")

    func getResult() {
        // 上下左右四个方向偏移量
        let offsets = [
            [-1, 0],
            [1, 0],
            [0, -1],
            [0, 1],
        ]
        for i in 0 ..< rows {
            for j in 0 ..< cols {
                if matrix[i][j] != 1 {
                    // 二维坐标(i, j) 转为 一维坐标pos
                    let pos = i * cols + j
                    if matrix[i][j] == 2 {
                        // 收集小华，小为的位置
                        huawei.append(pos)
                    } else if matrix[i][j] == 3 {
                        // 收集餐厅的位置
                        restaurants.append(pos)
                    }

                    for offset in offsets {
                        let newI = i + offset[0]
                        let newJ = j + offset[1]
                        if
                            newI >= 0 &&
                            newI < rows &&
                            newJ >= 0 &&
                            newJ < cols &&
                            matrix[newI][newJ] != 1
                        {
                            // 如果(i,j)和（newI,newJ）位置都是非1，则合并
                            ufs.union(pos, newI * cols + newJ)
                        }
                    }
                }
            }
        }
    }

    // 并查集实现
    class UnionFindSet {
        var father: [Int] = []

        init(_ N: Int) {
            father = Array(repeating: 0, count: N)
            for i in 0 ..< N {
                father[i] = i
            }
        }

        func find(_ xPoint: Int) -> Int {
            if xPoint != father[xPoint] {
                father[xPoint] = find(father[xPoint])
                return father[xPoint]
            }
            return xPoint
        }

        // 合并接触 如 F(1) = 0, F(3) = 0 ==> 代表 1与0, 3与0接触 等情况
        func union(_ xPoint: Int, _ yPoint: Int) {
            let xPoint_v = find(xPoint)
            let yPoint_v = find(yPoint)
            if xPoint_v != yPoint_v {
                father[yPoint_v] = xPoint_v
            }
        }
    }
}