There is a 2D grid of size n x n where each cell of this grid has a lamp that is initially turned off.
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.
When a lamp is turned on, it illuminates its cell and all other cells in the same row, column, or diagonal.
You are also given another 2D array queries, where queries[j] = [rowj, colj]. For the jth query, determine whether grid[rowj][colj] is illuminated or not. After answering the jth 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].
Return an array of integers ans, where ans[j] should be 1 if the cell in the jth query was illuminated, or 0 if the lamp was not.
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.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 2:
Input: n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,1]] Output: [1,1]
Example 3:
Input: n = 5, lamps = [[0,0],[0,4]], queries = [[0,4],[0,1],[1,4]] Output: [1,1,0]
Constraints:
1 <= n <= 1090 <= lamps.length <= 200000 <= queries.length <= 20000lamps[i].length == 20 <= rowi, coli < nqueries[j].length == 20 <= rowj, colj < n
class Solution:
def gridIllumination(
self, n: int, lamps: List[List[int]], queries: List[List[int]]
) -> List[int]:
points = set()
rcnt, ccnt, dgcnt, udgcnt = Counter(), Counter(), Counter(), Counter()
for r, c in lamps:
if (r, c) not in points:
points.add((r, c))
rcnt[r] += 1
ccnt[c] += 1
dgcnt[r - c] += 1
udgcnt[r + c] += 1
ans = [0] * len(queries)
for i, q in enumerate(queries):
r, c = q
if rcnt[r] or ccnt[c] or dgcnt[r - c] or udgcnt[r + c]:
ans[i] = 1
for a, b in [
(0, 1),
(1, 0),
(0, -1),
(-1, 0),
(0, 0),
(1, 1),
(-1, 1),
(1, -1),
(-1, -1),
]:
x, y = r + a, c + b
if (x, y) in points:
points.remove((x, y))
rcnt[x] -= 1
ccnt[y] -= 1
dgcnt[x - y] -= 1
udgcnt[x + y] -= 1
return ansclass Solution {
public int[] gridIllumination(int n, int[][] lamps, int[][] queries) {
Set<Long> points = new HashSet<>();
Map<Integer, Integer> rcnt = new HashMap<>();
Map<Integer, Integer> ccnt = new HashMap<>();
Map<Integer, Integer> dgcnt = new HashMap<>();
Map<Integer, Integer> udgcnt = new HashMap<>();
for (int[] l : lamps) {
int r = l[0], c = l[1];
long v = r * n + c;
if (!points.contains(v)) {
points.add(v);
rcnt.put(r, rcnt.getOrDefault(r, 0) + 1);
ccnt.put(c, ccnt.getOrDefault(c, 0) + 1);
dgcnt.put(r - c, dgcnt.getOrDefault(r - c, 0) + 1);
udgcnt.put(r + c, udgcnt.getOrDefault(r + c, 0) + 1);
}
}
int[][] dirs
= {{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {0, 0}, {1, 1}, {-1, 1}, {1, -1}, {-1, -1}};
int[] ans = new int[queries.length];
for (int i = 0; i < queries.length; ++i) {
int r = queries[i][0], c = queries[i][1];
if (rcnt.getOrDefault(r, 0) > 0 || ccnt.getOrDefault(c, 0) > 0
|| dgcnt.getOrDefault(r - c, 0) > 0 || udgcnt.getOrDefault(r + c, 0) > 0) {
ans[i] = 1;
for (int[] d : dirs) {
int x = r + d[0], y = c + d[1];
long v = x * n + y;
if (x < 0 || x >= n || y < 0 || y >= n || !points.contains(v)) {
continue;
}
points.remove(v);
rcnt.put(x, rcnt.get(x) - 1);
if (rcnt.get(x) == 0) {
rcnt.remove(x);
}
ccnt.put(y, ccnt.get(y) - 1);
if (ccnt.get(y) == 0) {
ccnt.remove(y);
}
dgcnt.put(x - y, dgcnt.get(x - y) - 1);
if (dgcnt.get(x - y) == 0) {
dgcnt.remove(x - y);
}
udgcnt.put(x + y, udgcnt.get(x + y) - 1);
if (udgcnt.get(x + y) == 0) {
udgcnt.remove(x + y);
}
}
}
}
return ans;
}
}function gridIllumination(
n: number,
lamps: number[][],
queries: number[][],
): number[] {
let lights: Set<string> = new Set();
let rows: Map<number, number> = new Map(); // i
let cols: Map<number, number> = new Map(); // j
let mainDiagonal: Map<number, number> = new Map(); // i - j
let subDiagonal: Map<number, number> = new Map(); // i + j
for (let [i, j] of lamps) {
let key = `${i},${j}`;
if (lights.has(key)) continue;
lights.add(key);
rows.set(i, (rows.get(i) || 0) + 1);
cols.set(j, (cols.get(j) || 0) + 1);
mainDiagonal.set(i - j, (mainDiagonal.get(i - j) || 0) + 1);
subDiagonal.set(i + j, (subDiagonal.get(i + j) || 0) + 1);
}
let ans: Array<number> = [];
let directions = [
[-1, -1],
[-1, 0],
[-1, 1],
[0, -1],
[0, 0],
[0, 1],
[1, -1],
[1, 0],
[1, 1],
];
for (let [i, j] of queries) {
// check
const check =
lights.has(`${i},${j}`) ||
rows.get(i) ||
cols.get(j) ||
mainDiagonal.get(i - j) ||
subDiagonal.get(i + j);
ans.push(check ? 1 : 0);
// close lamp
for (let [dx, dy] of directions) {
const [x, y] = [i + dx, j + dy];
let key = `${x},${y}`;
if (x < 0 || x > n - 1 || y < 0 || y > n - 1 || !lights.has(key)) {
continue;
}
lights.delete(key);
rows.set(x, rows.get(x) - 1);
cols.set(y, cols.get(y) - 1);
mainDiagonal.set(x - y, mainDiagonal.get(x - y) - 1);
subDiagonal.set(x + y, subDiagonal.get(x + y) - 1);
}
}
return ans;
}