Grid illumination


  • 1
    E

    Grid Illumination:

    Given an NxN grid with an array of lamp coordinates. Each
    lamp provides illumination to every square on their x axis, every square on
    their y axis, and every square that lies in their diagonal (think of a Queen in
    chess). Given an array of query coordinates, determine whether that point is
    illuminated or not. The catch is when checking a query all lamps adjacent to, or
    on, that query get turned off. The ranges for the variables/arrays were about:
    10^3 < N < 10^9, 10^3 < lamps < 10^9, 10^3 < queries < 10^9.


  • 0
    E

    Initially I thought this might be like the "Bomb Enemy" question that Google has. Looks like it is not.

    It doesn't even look like something that could use Union-Find algorithm.

    Any smart ideas for this one? I am just stuck.


  • 0

    @EnigmaTrance Can you explain better what the "catch" means, especially this sentence : "The catch is when checking a query all lamps adjacent to, or on, that query get turned off. "? For example there is a query for point (4,5), how do we define adjacent to this point lamps?
    Could you provide an examplе?


  • 0
    E

    @elmirap Sure.
    Basically when (4,5) is checked, then the 8 surrounding spots (3, 4), (3, 5), (3, 6), (4, 4), (4, 6), (7,4), (7,5), (7,6) all get turned off.


  • 0

    @EnigmaTrance. I think that the problem says that only adjacent lamps get turned off when a query is made. This means that lamps which are turned off don't provide illumination in their iillumination range (x,y,coord,diagonals) while query is in progress. At least this is the way I understand the problem.
    So here is my strategy. Count number of lamps in each horizontal, vertical and diagonal and store in map. On each query I count the lamps in adjacent 8 cells and check if lamps in given vertical, horizontal or diagonal are more than these in adjacent cells. If it is, I will return true, because there is at least one lamp except these in adjacent cells which illuminates the query point.


  • 0
    E

    I did not quite understand what the expected output is? Any example someone could post?


  • 0
    P

    @elmirap said in Grid illumination:

    So here is my strategy. Count number of lamps in each horizontal, vertical and diagonal and store in map. On each query I count the lamps in adjacent 8 cells and check if lamps in given vertical, horizontal or diagonal are more than these in adjacent cells. If it is, I will return true, because there is at least one lamp except these in adjacent cells which illuminates the query point.

    This is smart.

    This is


Log in to reply
 

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