题目
在大小为 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 。然后，关闭红色矩形中的所有灯。 • 1
示例 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]
解题
方法一：哈希
我们可以设计四个记录器(4个哈希map)。之所以设计记录器是因为，每点亮一个灯，就必然会点亮“一行”，“一列”，“一个正对角线”，“一个反对角线”。我们不再需要去记录每一个格子的“光源亮度”（会超时）。
如果两盏同一行的灯，所处的行的计数就会变成2。这意味着，只有当两盏灯同时熄灭，才能让这一行的计数变成0（也就是变黑）。
查询的时候，只要行、列、正对角、反对角任何一个有光源，必定导致该格子是亮的。然后删除8邻域（或当前）内的灯就行了。
struct hash_fn{ size_t operator()(const pair<int,int>&p)const{ static hash<long long> hash_ll; return hash_ll(p.first+(static_cast<long long>(p.second)<<32)); } }; class Solution { public: unordered_map<int,int> rows;//行哈希 unordered_map<int,int> cols;//列哈希 unordered_map<int,int> postive;//正对角线哈希 unordered_map<int,int> negative;//副对角线哈希 unordered_set<pair<int,int>,hash_fn> lampSet;//集合（记录灯的位置） vector<int> gridIllumination(int n, vector<vector<int>>& lamps, vector<vector<int>>& queries) { // auto hash_fn=[](const pair<int,int>&p)->size_t{ // static hash<long long> hash_ll; // return hash_ll(p.first+(static_cast<long long>(p.second)<<32)); // }; // unordered_set<pair<int,int>,decltype(hash_fn)> lampSet(0,hash_fn); for(vector<int>& lamp:lamps){ int row=lamp[0]; int col=lamp[1]; if(lampSet.count(pair<int,int>(row,col))) continue;//可能有重复的灯（测试样例比较恶心） rows[row]++; cols[col]++; postive[row-col]++; negative[col+row]++; lampSet.insert({row,col}); } vector<int> res; for(vector<int>& query:queries){ res.push_back(state(query[0],query[1]));//查询 turnOff(query[0],query[1],n);//关灯 } return res; } //获取当前状态（是否照明） bool state(int row,int col){ return bool(rows[row]+cols[col]+postive[row-col]+negative[col+row]); } //关灯（当前和八邻域） void turnOff(int row,int col,int n){ for(int i:{-1,0,1}){ if(row+i>=0&&row+i<n){ for(int j:{-1,0,1}){ if(col+j>=0&&col+j<n){ if(lampSet.count(pair<int,int>(row+i,col+j))){ lampSet.erase(pair<int,int>(row+i,col+j)); rows[row+i]--; cols[col+j]--; postive[row+i-col-j]--; negative[col+j+row+i]--; } } } } } } };
