【LeetCode每日一题】1001. 网格照明【困难】哈希

在大小为 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： alt 输入：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 。然后，关闭红色方框中的所有灯。

alt 第 1 次查询检查 grid[1][0] 是否被照亮（蓝色方框）。该单元格没有被照亮，所以 ans[1] = 0 。然后，关闭红色矩形中的所有灯。 alt

示例 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 <= 109 0 <= lamps.length <= 20000 0 <= queries.length <= 20000 lamps[i].length == 2 0 <= rowi, coli < n queries[j].length == 2 0 <= rowj, colj < n

题解：

这道题一开始的想法是使用一个二维数组去存下每一个坐标，但是这道题的范围太大，如果将每一个方格是否点亮都记录一遍一定会内存超限和超时，后来想到可以用map直接将该灯泡所在行、列、对角线的情况直接存下，开4个map存就可以了。这道题的另一个坑点在于，灯可能被重复点亮，这时候需要跳过这盏灯，否则会出现重复相加的情况。

class Solution {
public:
    vector<int> gridIllumination(int n, vector<vector<int>>& lamps, vector<vector<int>>& queries) {
        map<pair<int, int>, int> visP;
        unordered_map<long long, long long> visRow;
        unordered_map<long long, long long> visCol;
        unordered_map<long long, long long> viszuoxie;
        unordered_map<long long, long long> visyouxie;
        for(auto lamp: lamps){
            int x = lamp[0], y = lamp[1];
            if(visP[{x, y}]) continue;
            visP[{x, y}] = 1;
            visRow[x]++;
            visCol[y]++;
            viszuoxie[x - y]++;
            visyouxie[x + y]++;
        }
        vector<int> ans;
        for(auto query: queries){
            int x = query[0], y = query[1];
            if(visRow[x] || visCol[y] || viszuoxie[x - y] || visyouxie[x + y]){
                ans.push_back(1);
            }
            else ans.push_back(0);
            for(int r = x - 1; r <= x + 1; r++){
                for(int c = y - 1; c <= y + 1; c++){
                    if(r < 0 || r >= n || c < 0 || c >= n) continue;
                    if(visP[{r, c}]){
                        visP[{r, c}]--;
                        visRow[r]--;
                        visCol[c]--;
                        viszuoxie[r - c]--;
                        visyouxie[r + c]--;
                    }
                }
            }
        }
        return ans;
    }
};