Give a list of bomb, each mine has 3 numbers, x, y coordinates and explosion range. Find the initial mine that can eventually detonate the most mines

Question

Give a list of mines, each mine contains 3 numbers, x, y coordinates and explosion range . Find the initial mine that can eventually detonate the most mines and maximum number of mine it denotes.

the x, y coordinates can be negative numbers and all three numbers can be double.

I coded a dfs solution but got incorrect result. Does it seem like an ok implementation . Any inputs will be helpful.

List<Node> list;
    RadiusBlast(List<Node> list){
        this.list = list;
    }

    static boolean isInside(int circle_x, int circle_y,
                            int rad, int x, int y)
    {
        // Compare radius of circle with
        // distance of its center from
        // given point
        //System.out.println("source:"+ circle_x + "," + circle_y);
        if ((x - circle_x) * (x - circle_x) +
                (y - circle_y) * (y - circle_y) <= rad * rad) {

            //System.out.println("isInside:"+ x + "," + y);
            return true;
        }
        else
            return false;
    }


    public int dfs2(int i,Node node,boolean[] visited) {
        //System.out.println("dfs");
        visited[i] = true;
        int res = 1;
        for(Node newNode : list){
            if(!visited[newNode.index]) {
                if (isInside(node.x, node.y, node.r, newNode.x, newNode.y))
                    res += dfs2(newNode.index,node,visited);
            }

        }

        return res;
    }

    static class Node{
        int x,y,r ;
        int index;
        boolean depthvisited;
        //boolean visited;

        public Node(int x, int y, int r,int index) {
            this.x = x;
            this.y = y;
            this.r = r;
            this.index = index;
        }
    }

    // Driver Program to test above function
    public static void main(String arg[])
    {
        //RadiusBlast r = new RadiusBlast();

        int x = -1, y = 3;
        x = 2 ; y = 3;
        int x1 = 2 ; int y2 = 3 ;

        int circle_x = 0, circle_y = 7, rad = 5;

       if (isInside(circle_x, circle_y, rad, x, y))
            System.out.println("Inside1 main");
        else
            System.out.println("Outside");

        if (isInside(circle_x, circle_y, rad, x1, y2))
            System.out.println("Inside2 main");
        else
            System.out.println("Outside ");

        //x1, y1, r1
        // 2,3,3
        // -1,3,2
        // 3,2,5
        List<Node> list = new ArrayList<Node>();

        list.add(new Node(2,3,3,0));
        list.add(new Node(2,3,1,1));
        list.add(new Node(0,7,5,2));

        boolean[] visited;

        RadiusBlast r = new RadiusBlast(list);
        int res =0 ;
        for(int i =0; i < list.size(); i++){
               visited = new boolean[list.size()];
               res = Math.max(res,r.dfs2(list.get(i).index,list.get(i),visited));
               //System.out.println("res:" + (res));
        }
        System.out.println("result:" + (res - 1));

    }

Answer 1

Iterate over mines list and explode each mine recursively. Collect exploded count and pick maximum one. Something like this:

public class Test {
    public static void main(String[] args) throws Exception {
        List<Node> list = new ArrayList<Node>();

        list.add(new Node(2, 3, 3, 0));
        list.add(new Node(2, 3, 1, 1));
        list.add(new Node(0, 7, 5, 2));

        System.out.println("Deadliest node is: " + findDeadliest(list).index);
    }

    public static Node findDeadliest(List<Node> mines) {
        Node result = mines.get(0);
        for(Node n : mines) {
            List<Node> exploded = new ArrayList<>();
            explode(n, mines, exploded);
            n.triggeredCount = exploded.size();
            result = (n.triggeredCount > result.triggeredCount) ? n : result; 
        }
        return result;
    }

    public static void explode(Node mine, List<Node> mines, List<Node> exploded){
        for(Node target: mines) {
            if(!exploded.contains(target)) {
                if(isInside(mine, target)) {
                    exploded.add(target);
                    explode(target, mines, exploded);
                }
            }
        }
    }
    static boolean isInside(Node s, Node t) {
        double d = Math.pow(s.r,2) - ( Math.pow(s.x-t.x, 2) + Math.pow(s.y-t.y, 2));
        return d>0;
    }
}

class Node {
    @Override
    public int hashCode() {
        return this.index;
    }

    @Override
    public boolean equals(Object obj) {
        if(obj instanceof Node) {
            return this.index == ((Node)obj).index;
        } 
        return false;
    }

    int x, y, r;
    int index;
    int triggeredCount;

    public Node(int x, int y, int r, int index) {
        this.x = x;
        this.y = y;
        this.r = r;
        this.index = index;
    }
}

Output:

Deadliest node is: 2

Modify the code as per your needs. Do the null checks and error handling.

Answer 2

There might be some improvements to search with memorization in this problem - we don't really need to search again if the detonated bombs have been calculated before.

  memory = [-1] * N
  visited = [False] * N
  def count_explosion(source):
    if memory[source] != -1:
      return memory[source]
    accu = 1
    visited[source] = True
    for k in range(N):
      if source == k:
        continue
      if adjacent[source][k] and not visited[k]:
        if memory[k] != -1:
          accu += memory[k]
        else:
          accu += count_explosion(k)
    memory[source] = accu
    return accu

  max_num = 1
  for i in range(N):
    max_num = max(max_num, count_explosion(i))
  return max_num

Note the adjacent is the matrix to store the directed graph, where we pre-process using the euclidean distance. We need a visited here as well to avoid cyclic cases.