欢乐的周末（C++ ）刷题记录

2023题库目录

链接2023华为OD备考【转载】

题目描述

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

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

输入描述

第一行输入m和n，m代表地图的长度，n代表地图的宽度。

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

0 为通畅的道路

1 为障碍物（且仅1为障碍物）

2 为小华或者小为，地图中必定有且仅有2个 （非障碍物）

3 为被选中的聚餐地点（非障碍物）

输出描述

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

用例

备注：

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

4 <= m <= 100

4 <= n <= 100

聚餐的地点数量为 k，则

1< k <= 100

C++

#include <iostream>
#include <vector>
using namespace std;

// 并查集实现
class UnionFindSet {
private:
    vector<int> fa;

public:
    UnionFindSet(int n) {
        fa.resize(n);
        for (int i = 0; i < n; i++) fa[i] = i;
    }

    int find(int x) {
        if (x != fa[x]) {
            fa[x] = find(fa[x]);
            return fa[x];
        }
        return x;
    }

    void merge(int x, int y) {
        int x_fa = find(x);
        int y_fa = find(y);

        if (x_fa != y_fa) {
            fa[y_fa] = x_fa;
        }
    }
};

int main() {
    int m, n;
    cin >> m >> n;
    vector<vector<int>> matrix(n, vector<int>(m, 0));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> matrix[i][j];
        }
    }

    UnionFindSet ufs(n * m);

    vector<int> huawei; // 记录小华位置
    vector<int> restaurants; // 记录聚餐地点位置

    vector<vector<int>> offsets = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 偏移量

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (matrix[i][j] != 1) { // 如果是障碍物则不处理
                int x = i * m + j; // 将二维坐标转换为一维坐标
                if (matrix[i][j] == 2) huawei.push_back(x); // 记录小华位置
                else if (matrix[i][j] == 3) restaurants.push_back(x); // 记录聚餐地点位置

                for (auto offset : offsets) { // 遍历四个方向
                    int newI = i + offset[0];
                    int newJ = j + offset[1];
                    if (newI >= 0 && newI < n && newJ >= 0 && newJ < m && matrix[newI][newJ] != 1) {
                        ufs.merge(x, newI * m + newJ); // 合并连通块
                    }
                }
            }
        }
    }

    int hua_fa = ufs.find(huawei[0]); // 获取小华所在连通块的祖先
    int wei_fa = ufs.find(huawei[1]); // 获取小为所在连通块的祖先

    if (hua_fa != wei_fa) { // 如果小华和小为不在同一个连通块中，说明没有共同到达的聚餐地点
        cout << 0 << endl;
        return 0;
    }

    int ans = 0;
    for (auto restaurant : restaurants) { // 遍历所有聚餐地点
        if (ufs.find(restaurant) == hua_fa) { // 如果聚餐地点和小华在同一个连通块中
            ans++; // 答案加一
        }
    }

    cout << ans << endl; // 输出答案

    return 0;
}