在大小为 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 表示未照亮。
示例 1：
输入：n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]]
输出：[1,0]
解释：最初所有灯都是关闭的。在执行查询之前，打开位于 [0, 0] 和 [4, 4] 的灯。第 0 次查询检查 grid[1][1] 是否被照亮（蓝色方框）。该单元格被照亮，所以 ans[0] = 1 。然后，关闭红色方框中的所有灯。
第 1 次查询检查 grid[1][0] 是否被照亮（蓝色方框）。该单元格没有被照亮，所以 ans[1] = 0 。然后，关闭红色矩形中的所有灯。
示例 2：
输入：n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,1]]
输出：[1,1]
示例 3：
输入：n = 5, lamps = [[0,0],[0,4]], queries = [[0,4],[0,1],[1,4]]
输出：[1,1,0]
提示：
1 <= n <= 10^90 <= lamps.length <= 200000 <= queries.length <= 20000lamps[i].length == 20 <= rowi, coli < nqueries[j].length == 20 <= rowj, colj < n 分析：
方法：哈希表
因为 n 最大为 10^9，如果用二维数组，空间复杂度最大就是 10^18，一定会超内存，那么我们可以用 哈希表 的方式来存储每一行，列，两对角线的灯的个数，这样空间复杂度最大就为 10^9，行用横坐标，列用纵坐标，左对角线用横纵之和，右对角线用横纵之差，关灯的时候只需要所有哈希表对应值减一就可以了。
关于 lamps，如果每次找灯都遍历一次，太浪费时间，因此我们将二维数组转化为一维的集合，假设查找的坐标为 （i，j），lamps 边长为 n，那么就可以表示为 i * n + j，这样每次找灯只需要调用集合相关方法即可，还可以防止哈希表存储时出现重复灯的情况。
关于找周围的灯，我们可以定义一个二维数组表示自身和周围八格的横纵坐标的差值，找灯时只需要遍历该数组，将差值加到当前坐标即可。
时间复杂度：O(m + n) m，n 为 lamps，queries 的长度
空间复杂度：O(m)
class Solution {
public int[] gridIllumination(int n, int[][] lamps, int[][] queries) {
//创建HashMap分别存储 行，列，左右对角线的灯
HashMap row = new HashMap<>(), col = new HashMap<>(), left = new HashMap<>(), right = new HashMap<>();
//创建集合，存储灯
HashSet set = new HashSet<>();
//遍历，存储灯
for(int[] lamp: lamps){
//避免添加多余的灯
if(set.contains(lamp[0] * (long) n + lamp[1])){
continue;
}
//行
storage(row, lamp[0]);
//列
storage(col, lamp[1]);
//左对角线
storage(left, lamp[0] + lamp[1]);
//右对角线
storage(right, lamp[0] - lamp[1]);
//二维转一维存储
set.add(lamp[0] * (long) n + lamp[1]);
}
//记录照明情况
int[] res = new int[queries.length];
//定义当前格和周围八格
int[][] surrounds = new int[][]{{0, 0}, {0, -1}, {0, 1}, {-1, 0}, {-1, -1}, {-1, 1}, {1, 0}, {1, 1}, {1, -1}};
//遍历 queries 数组，记录照明情况，关灯
for(int i = 0; i < queries.length; ++i){
//记录两数
int j = queries[i][0], k = queries[i][1];
//判断是否被照明
if(row.containsKey(j) || col.containsKey(k) || left.containsKey(j + k) || right.containsKey(j - k)){
res[i] = 1;
}else{
res[i] = 0;
}
//关灯
for(int[] sur: surrounds){
//当前位置
int a = j + sur[0], b = k + sur[1];
//越界
if(a < 0 || b < 0 || a > n-1 || b > n-1){
continue;
}
//有灯，关灯
if(set.contains(a * (long) n + b)){
//删除此灯
set.remove(a * (long) n + b);
//行
close(row, a);
//列
close(col, b);
//左对角线
close(left, a + b);
//右对角线
close(right, a - b);
}
}
}
return res;
}
//存储灯的方法
public void storage(HashMap map, int key){
map.put(key, map.getOrDefault(key, 0) + 1);
}
//关灯
public void close(HashMap map, int key){
if(map.get(key) == 1){
map.remove(key);
}
else{
map.put(key, map.get(key)-1);
}
}
}
题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/grid-illumination
