sensor detection game

  • 0

    Imagine there is a 2d plane with (0,0) as left-bottom corner and (1,1) as right-top corner. Suppose there are several sensor with(radius, x, y) placed inside this plane. write a function to check if a player can reach (1,1) from (0,0) without being detected by anysensors. input is List<sensor> list, with sensor( double radius, double x ,double y)

    Hint: using DFS is the easiest way

  • 0

    I was thinking the same, using DFS. There is another slightly different problem than this , when there is no X constraint.

  • 1

    @elmirap we can model every overlapped coverage as connected graph node

  • 0

    @daniel.w.1 yes, you should check the connected components, the most important circles are tangents to the boundaries

  • 2

    I think your idea is smart. If we build graph and can find a connected component connect at least two boundaries of the plane(except left&&up, down&&right) then you can't find a path to your destination.
    Otherwise there is always a path to the destination.

    Correct me if it has defects.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.