#1001
Grid Illumination
master · 1750 · lc hard +32 · verified · 39.1% accepted · 648 likes · top 18%
Description
On an n x n grid with initially unlit lamps, you are given lamps[i] = [rowi, coli] indicating which lamps are turned on. A lit lamp illuminates its entire row, column, and both diagonals.
For each query queries[j] = [rowj, colj], determine if that cell is illuminated (1) or not (0). After answering each query, switch off the lamp at that cell and all 8 of its neighbors.
Return an integer array ans of query results.
Example 1:
Input: n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]]
Output: [1,0]
Explanation: We have the initial grid with all lamps turned off. In the above picture we see the grid after turning on the lamp at grid[0][0] then turning on the lamp at grid[4][4].
The 0th query asks if the lamp at grid[1][1] is illuminated or not (the blue square). It is illuminated, so set ans[0] = 1. Then, we turn off all lamps in the red square.
Example 2:
The 1st query asks if the lamp at grid[1][0] is illuminated or not (the blue square). It is not illuminated, so set ans[1] = 0. Then, we turn off all lamps in the red rectangle.
Example 3:
Input: n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,1]]
Output: [1,1]
Example 4:
Input: n = 5, lamps = [[0,0],[0,4]], queries = [[0,4],[0,1],[1,4]]
Output: [1,1,0]
Code
1
2
3