题目描述

在 N x N 的网格上，每个单元格 (x, y) 上都有一盏灯，其中 0 <= x < N 且 0 <= y < N。

最初，一定数量的灯是亮着的。lamps[i] 告诉我们亮着的第 i 盏灯的位置。每盏灯都照亮其所在 x 轴、y 轴和两条对角线上的每个正方形（类似于国际象棋中的皇后）。

对于第 i 次查询 queries[i] = (x, y)，如果单元格 (x, y) 是被照亮的，则查询结果为 1，否则为 0 。

在每个查询 (x, y) 之后 [按照查询的顺序]，我们关闭位于单元格 (x, y) 上或其相邻 8 个方向上（与单元格 (x, y) 共享一个角或边）的任何灯。

返回答案数组 answer。每个值 answer[i] 应等于第 i 次查询 queries[i] 的结果。

样例

输入：N = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]]
输出：[1,0]
解释： 
在执行第一次查询之前，我们位于 [0, 0] 和 [4, 4] 灯是亮着的。
表示哪些单元格亮起的网格如下所示，其中 [0, 0] 位于左上角：
1 1 1 1 1
1 1 0 0 1
1 0 1 0 1
1 0 0 1 1
1 1 1 1 1
然后，由于单元格 [1, 1] 亮着，第一次查询返回 1。在此查询后，位于 [0，0] 处的灯将关闭，网格现在如下所示：
1 0 0 0 1
0 1 0 0 1
0 0 1 0 1
0 0 0 1 1
1 1 1 1 1
在执行第二次查询之前，我们只有 [4, 4] 处的灯亮着。现在，[1, 0] 处的查询返回 0，因为该单元格不再亮着。

注意

• 1 <= N <= 10^9
• 0 <= lamps.length <= 20000
• 0 <= queries.length <= 20000
• lamps[i].length == queries[i].length == 2

算法

(哈希表) $O(lamps.length + queries.length)$

1. 建立四个哈希表，分别记录每一行中灯的位置，每一列中灯的位置，每个对角线中灯的位置以及每个反对角线中等的位置。
2. 具体地，对于 “行” 哈希表，key 为行号，value 为一个无序集合，记录有灯位置所在的列号；其他哈希表同理。
3. 在查询前将所有的灯的位置插入到哈希表中。
4. 查询时，分别询问四个哈希表中对应的行、列、对角线和反对角线是否有灯。如果有，则记录 1；否则记录 0。删除时，枚举 9 个位置，如果存在于哈希表中，则删除对应的灯。

时间复杂度

• 哈希表和无序集合的增删改查单次操作时间复杂度都是 $O(1)$，故插入需要 $O(lamps.length)$ 的时间，查询和删除需要 $O(queries.length)$ 的时间。总时间复杂度为 $O(lamps.length + queries.length)$。

空间复杂度

• 需要四个哈希表来记录灯的位置，但总共有 $lamps.length$ 盏灯，故总空间复杂度为 $O(lamps.length)$。

C++ 代码

class Solution {
public:
    vector<int> gridIllumination(int N, vector<vector<int>>& lamps, vector<vector<int>>& queries) {
        unordered_map<int, unordered_set<int>> row, col, dig, rdig;
        for (auto &l : lamps) {
            row[l[0]].insert(l[1]);
            col[l[1]].insert(l[0]);
            dig[l[0] + l[1]].insert(l[0]);
            rdig[l[0] - l[1]].insert(l[0]);
        }

        const int dx[9] = {0, 0, -1, -1, -1, 0, 1, 1, 1};
        const int dy[9] = {0, -1, -1, 0, 1, 1, 1, 0, -1};

        vector<int> ans;
        for (auto &q : queries) {
            int x = q[0], y = q[1];
            if (row[x].empty() && col[y].empty()
             && dig[x + y].empty() && rdig[x - y].empty())
                ans.push_back(0);
            else
                ans.push_back(1);

            for (int i = 0; i < 9; i++) {
                int tx = x + dx[i], ty = y + dy[i];
                if (tx < 0 || tx >= N || ty < 0 || ty >= N)
                    continue;

                row[tx].erase(ty);
                col[ty].erase(tx);
                dig[tx + ty].erase(tx);
                rdig[tx - ty].erase(tx);
            }
        }
        return ans;
    }
};