1001. Grid Illumination Hard

1/**
2 * [1001] Grid Illumination
3 *
4 * There is a 2D grid of size n x n where each cell of this grid has a lamp that is initially turned off.
5 * You are given a 2D array of lamp positions lamps, where lamps[i] = [rowi, coli] indicates that the lamp at grid[rowi][coli] is turned on. Even if the same lamp is listed more than once, it is turned on.
6 * When a lamp is turned on, it illuminates its cell and all other cells in the same row, column, or diagonal.
7 * You are also given another 2D array queries, where queries[j] = [rowj, colj]. For the j^th query, determine whether grid[rowj][colj] is illuminated or not. After answering the j^th query, turn off the lamp at grid[rowj][colj] and its 8 adjacent lamps if they exist. A lamp is adjacent if its cell shares either a side or corner with grid[rowj][colj].
8 * Return an array of integers ans, where ans[j] should be 1 if the cell in the j^th query was illuminated, or 0 if the lamp was not.
9 *  
10 * Example 1:
11 * <img alt="" src="https://assets.leetcode.com/uploads/2020/08/19/illu_1.jpg" style="width: 750px; height: 209px;" />
12 * Input: n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]]
13 * Output: [1,0]
14 * 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].
15 * The 0^th 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.
16 * <img alt="" src="https://assets.leetcode.com/uploads/2020/08/19/illu_step1.jpg" style="width: 500px; height: 218px;" />
17 * The 1^st 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.
18 * <img alt="" src="https://assets.leetcode.com/uploads/2020/08/19/illu_step2.jpg" style="width: 500px; height: 219px;" />
19 * 
20 * Example 2:
21 * 
22 * Input: n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,1]]
23 * Output: [1,1]
24 * 
25 * Example 3:
26 * 
27 * Input: n = 5, lamps = [[0,0],[0,4]], queries = [[0,4],[0,1],[1,4]]
28 * Output: [1,1,0]
29 * 
30 *  
31 * Constraints:
32 * 
33 * 	1 <= n <= 10^9
34 * 	0 <= lamps.length <= 20000
35 * 	0 <= queries.length <= 20000
36 * 	lamps[i].length == 2
37 * 	0 <= rowi, coli < n
38 * 	queries[j].length == 2
39 * 	0 <= rowj, colj < n
40 * 
41 */
42pub struct Solution {}
43
44// problem: https://leetcode.com/problems/grid-illumination/
45// discuss: https://leetcode.com/problems/grid-illumination/discuss/?currentPage=1&orderBy=most_votes&query=
46
47// submission codes start here
48
49impl Solution {
50    pub fn grid_illumination(n: i32, lamps: Vec<Vec<i32>>, queries: Vec<Vec<i32>>) -> Vec<i32> {
51        vec![]
52    }
53}
54
55// submission codes end
56
57#[cfg(test)]
58mod tests {
59    use super::*;
60
61    #[test]
62    fn test_1001() {
63    }
64}
65