You are given a grid of size N x N, and each cell of this grid has a lamp that is initially turned off.
You are also given an array of lamp positions lamps, where lamps[i] = [rowi, coli] indicates that the lamp at grid[rowi][coli] is turned on. When a lamp is turned on, it illuminates its cell and all other cells in the same row, column, or diagonal.
Finally, you are given a query array queries, where queries[i] = [rowi, coli]. For the ith query, determine whether grid[rowi][coli] is illuminated or not. After answering the ith query, turn off the lamp at grid[rowi][coli] and its 8 adjacent lamps if they exist. A lamp is adjacent if its cell shares either a side or corner with grid[rowi][coli].
Return an array of integers ans, where ans[i] should be 1 if the lamp in the ith 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.
class Solution {
public int[] gridIllumination(int N, int[][] lamps, int[][] queries) {
Set<List<Integer>> set = new HashSet();
for (int[] lamp : lamps) {
set.add(Arrays.asList(lamp[0], lamp[1]));
}
int[] res = new int[queries.length];
int[] dx = new int[]{-1, -1, -1, 0, 0, 0, 1, 1, 1};
int[] dy = new int[]{-1, 0, 1, -1, 0, 1, -1, 0, 1};
for (int i = 0; i < queries.length; i ++) {
int[] query = queries[i];
for (List<Integer> lamp : set) {
if (covered(query, lamp)) {
res[i] = 1;
break;
}
}
for (int k = 0; k < 9; k ++) {
int nx = query[0] + dx[k];
int ny = query[1] + dy[k];
if (nx >= 0 && nx < N && ny >= 0 && ny < N) {
set.remove(Arrays.asList(nx, ny));
}
}
}
return res;
}
private boolean covered(int[] query, List<Integer> lamp) {
int i = query[0], j = query[1];
int x = lamp.get(0), y = lamp.get(1);
if (i == x || j == y) return true;
if (Math.abs(i - x) == Math.abs(j - y)) return true;
return false;
}
}
class Solution {
public int[] gridIllumination(int N, int[][] lamps, int[][] queries) {
Set<List<Integer>> set = new HashSet();
Map<Integer, Integer> rows = new HashMap();
Map<Integer, Integer> cols = new HashMap();
Map<Integer, Integer> diag1 = new HashMap();
Map<Integer, Integer> diag2 = new HashMap();
for (int[] lamp : lamps) {
int x = lamp[0];
int y = lamp[1];
set.add(Arrays.asList(x, y));
rows.put(x, rows.getOrDefault(x, 0) + 1);
cols.put(y, cols.getOrDefault(y, 0) + 1);
diag1.put(x + y, diag1.getOrDefault(x + y, 0) + 1);
diag2.put(x - y, diag2.getOrDefault(x - y, 0) + 1);
}
int[] res = new int[queries.length];
int[] dx = new int[]{-1, -1, -1, 0, 0, 0, 1, 1, 1};
int[] dy = new int[]{-1, 0, 1, -1, 0, 1, -1, 0, 1};
for (int i = 0; i < queries.length; i ++) {
int[] query = queries[i];
int x = query[0];
int y = query[1];
if (rows.getOrDefault(x, 0) > 0 ||
cols.getOrDefault(y, 0) > 0 ||
diag1.getOrDefault(x + y, 0) > 0 ||
diag2.getOrDefault(x - y, 0) > 0
) {
res[i] = 1;
}
for (int k = 0; k < 9; k ++) {
int nx = x + dx[k];
int ny = y + dy[k];
if (nx >= 0 && nx < N && ny >= 0 && ny < N && set.contains(Arrays.asList(nx, ny))) {
set.remove(Arrays.asList(nx, ny));
rows.put(nx, rows.get(nx) - 1);
cols.put(ny, cols.get(ny) - 1);
diag1.put(nx + ny, diag1.get(nx + ny) - 1);
diag2.put(nx - ny, diag2.get(nx - ny) - 1);
}
}
}
return res;
}
}
