### 题目描述 在大小为 n x n 的网格 grid 上，每个单元格都有一盏灯，最初灯都处于 关闭 状态。 给你一个由灯的位置组成的二维数组 lamps ，其中 lamps[i] = [rowi, coli] 表示 打开 位于 grid[rowi][coli] 的灯。即便同一盏灯可能在 lamps 中多次列出，不会影响这盏灯处于 打开 状态。 当一盏灯处于打开状态，它将会照亮 自身所在单元格 以及同一 行 、同一 列 和两条 对角线 上的 所有其他单元格 。 另给你一个二维数组 queries ，其中 queries[j] = [rowj, colj] 。对于第 j 个查询，如果单元格 [rowj, colj] 是被照亮的，则查询结果为 1 ，否则为 0 。在第 j 次查询之后 [按照查询的顺序] ，关闭 位于单元格 grid[rowj][colj] 上及相邻 8 个方向上（与单元格 grid[rowi][coli] 共享角或边）的任何灯。 返回一个整数数组 ans 作为答案， ans[j] 应等于第 j 次查询 queries[j] 的结果，1 表示照亮，0 表示未照亮 ### 问题解答 #### 代码实现 ```java class Solution { public int[] gridIllumination(int n, int[][] lamps, int[][] queries) { HashMap<Integer, Integer> row = new HashMap<>(); HashMap<Integer, Integer> col = new HashMap<>(); HashMap<Integer, Integer> left = new HashMap<>(); HashMap<Integer, Integer> right = new HashMap<>(); HashSet<Integer> set = new HashSet<>(); for(int i=0;i<lamps.length;i++){ int x = lamps[i][0]; int y = lamps[i][1]; if(set.contains(x*n + y)) continue; row.put(x, row.getOrDefault(x, 0) + 1); col.put(y, col.getOrDefault(y, 0) + 1); left.put(x-y, left.getOrDefault(x-y, 0) + 1); right.put(x+y, right.getOrDefault(x+y, 0) + 1); set.add(x*n + y); } int[] res = new int[queries.length]; for(int i=0;i<queries.length;i++){ int x = queries[i][0]; int y = queries[i][1]; if(row.getOrDefault(x, 0)>0 || col.getOrDefault(y, 0)>0 || left.getOrDefault(x-y, 0)>0 || right.getOrDefault(x+y, 0)>0){ res[i] = 1; } // 查看3*3位置，如果有亮灯，熄灭他 int top = x - 1 >= 0 ? x - 1 : 0; int bottom = x + 1 < n ? x + 1 : n - 1; int left_l = y - 1 >= 0 ? y - 1 : 0; int right_r = y + 1 < n ? y + 1 : n - 1; for(int p=top;p<=bottom;p++){ for(int q=left_l;q<=right_r;q++){ // 该区域内包含，进行灭灯操作 if(set.contains(p*n + q)){ row.put(p, row.getOrDefault(p, 1)-1); col.put(q, col.getOrDefault(q, 1)-1); left.put(p-q, left.getOrDefault(p-q, 1)-1); right.put(p+q, right.getOrDefault(p+q, 1)-1); } // 把灯灭掉 set.remove(p*n + q); } } } return res; } } ``` 最后编辑：2024年04月23日 ©著作权归作者所有 赞 0 分享
最新回复