2024每日刷题(146)

Leetcode—2101. 引爆最多的炸弹

在这里插入图片描述

实现代码

typedef long long LL;

class Solution {
public:
    int maximumDetonation(vector<vector<int>>& bombs) {
        int n = bombs.size();
        unordered_map<int, vector<int>> adj;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(i == j) {
                    continue;
                }
                LL x1 = bombs[i][0];
                LL y1 = bombs[i][1];
                LL r1 = bombs[i][2];

                LL x2 = bombs[j][0];
                LL y2 = bombs[j][1];
                LL r2 = bombs[j][2];

                LL distance = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
                if(r1 * r1 >= distance) {
                    adj[i].push_back(j);
                }
            }
        }
        unordered_set<int> visited;

        function<void(int)> dfs = [&](int u) {
            visited.insert(u);
            for(int &v: adj[u]) {
                if(visited.find(v) == visited.end()) {
                    dfs(v);
                }
            }
        };

        int res = 0;
        for(int i = 0; i < n; i++) {
            dfs(i);
            int count = visited.size();
            res = max(count, res);
            visited.clear();
        }

        return res;
    }
};

运行结果

在这里插入图片描述

之后我会持续更新,如果喜欢我的文章,请记得一键三连哦,点赞关注收藏,你的每一个赞每一份关注每一次收藏都将是我前进路上的无限动力 !!!↖(▔▽▔)↗感谢支持!

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部