Java | BFS | Beats > 99.7% | With Comments
Intuition\n Describe your first thoughts on how to solve this problem. \nWe systematically explore each bomb and its surrounding bombs to determine the maximum 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe systematically explore each bomb and its surrounding bombs to determine the maximum number of bombs that can be detonated from each starting point. By performing BFS, we ensure that we consider all reachable bombs and maximize the count of detonations.\n\n\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n# Here\'s a step-by-step approach:\n\n1.The **isPossible** **function** determines whether a given bomb can detonate another bomb based on their positions and explosion ranges. It calculates the Euclidean distance between the bombs and compares it with the explosion range. If the distance is less than or equal to the explosion range, the bomb can detonate the other bomb.\n2.The **helper function** takes the array of bombs and a current bomb index as input. It iterates through all the other bombs, excluding the current bomb, and checks if the current bomb can detonate the surrounding bomb using the isPossible function. If it can, the index of the surrounding bomb is added to the indi_lst ArrayList.\n3.The **bfs function** performs a BFS traversal starting from a given bomb index. It initializes a queue and a visited array. It adds the starting bomb index to the queue, marks it as visited, increments the count, and then continues exploring its neighboring bombs. For each neighboring bomb, if it hasn\'t been visited yet, it adds it to the queue, marks it as visited, and increments the count. This process continues until the queue is empty.\n4.The **maximumDetonation function** is the main function that utilizes the helper and bfs functions. It iterates through each bomb in the given array. If a bomb has not been visited yet, it calls the bfs function to find the maximum number of bombs that can be detonated starting from that bomb. It keeps track of the maximum count of detonations across all bombs and returns it as the result.\n\n# Complexity\n- Time complexity:$$O(n^2)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:$$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nimport java.util.*;\n\nclass Solution {\n    //Function to know cur_bomb can explode the sur_bomb(current bomb, surounding bomb)\n    public static boolean isPossible(int[] cur_bomb, int[] sur_bomb) {\n        long cbx = cur_bomb[0];\n        long cby = cur_bomb[1];\n        long cbcap = cur_bomb[2];\n        long sbx = sur_bomb[0];\n        long sby = sur_bomb[1];\n        return (cbx - sbx) * (cbx - sbx) + (cby - sby) * (cby - sby) <= cbcap*cbcap;\n    }\n    //helper function to get the ArrayList of surrounding bombs the current bomb can effect.\n    public static ArrayList<Integer> helper(int[][] bombs, int cur) {\n        ArrayList<Integer> indi_lst = new ArrayList<>();\n        for (int i = 0; i < bombs.length; i++) {\n            if (i == cur) {\n                continue;\n            }\n            if (isPossible(bombs[cur], bombs[i])) {\n                indi_lst.add(i);\n            }\n        }\n        return indi_lst;\n    }\n    //bfs to find the maximum number of bombs the current bomb can explode.\n    public static int bfs(ArrayList<ArrayList<Integer>> lst, int i, boolean[] flag) {\n        int res = 0;\n        Queue<Integer> que = new LinkedList<>();\n        boolean[] cur_vis = new boolean[lst.size()];\n        que.add(i);\n        flag[i] = true;\n        cur_vis[i]=true;\n        res++;\n        while (!que.isEmpty()) {\n            int bmb = que.poll();\n            for (int tmp : lst.get(bmb)) {\n                if (!cur_vis[tmp]) {\n                    que.add(tmp);\n                    res++;\n                    cur_vis[tmp] = true;\n                    flag[tmp] = true;\n                }\n            }\n        }\n        return res;\n    }\n    //main function\n    public int maximumDetonation(int[][] bombs) {\n        int n = bombs.length;\n        ArrayList<ArrayList<Integer>> lst = new ArrayList<>(n);\n        for (int i = 0; i < n; i++) {\n            lst.add(helper(bombs, i));\n        }\n        int res = 0;\n        boolean[] flag = new boolean[n];\n        for (int i = 0; i < n; i++) {\n            if (!flag[i]) {\n                res = Math.max(res, bfs(lst, i, flag));\n            }\n        }\n        // System.out.println(lst);\n        return res;\n    }\n}\n```
['Breadth-First Search', 'Java']