欢乐的周末(C++ )刷题记录

2023题库目录

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

题目描述

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

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

输入描述

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

第二行开始具体输入地图信息,地图信息包含:

0 为通畅的道路

1 为障碍物(且仅1为障碍物)

2 为小华或者小为,地图中必定有且仅有2个 (非障碍物)

3 为被选中的聚餐地点(非障碍物)

输出描述

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

用例

输入4 4
2 1 0 3
0 1 2 1
0 3 0 0
0 0 0 0
输出2
说明

第一行输入地图的长宽为3和4。

第二行开始为具体的地图,其中:3代表小华和小明选择的聚餐地点;2代表小华或者小明(确保有2个);0代表可以通行的位置;1代表不可以通行的位置。

此时两者能都能到达的聚餐位置有2处。

输入4 4
2 1 2 3
0 1 0 0
0 1 0 0
0 1 0 0
输出0
说明

第一行输入地图的长宽为4和4。

第二行开始为具体的地图,其中:3代表小华和小明选择的聚餐地点;2代表小华或者小明(确保有2个);0代表可以通行的位置;1代表不可以通行的位置。

由于图中小华和小为之间有个阻隔,此时,没有两人都能到达的聚餐地址,故而返回0。

备注:

地图的长宽为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;
}
#华为信息集散地#
全部评论

相关推荐

吴offer选手:HR:我KPI到手了就行,合不合适关我什么事
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务