leetcode 1001 网格照明

题意

有一个 $n \times n$ 的矩阵 $(n < 1e9)$ ，每个位置上有一个灯，给出一个灯位置序列，表示依次打开这些灯。每个灯可以照亮同一行同一列还有两条对角线上的所有格子。再给出一个位置序列，表示查询每个位置是否被照亮，同时对于每个询问位置，如果该位置加上周围八个格子里面有亮着的灯，就把这些亮灯熄灭。

做法

注意题意，灯只会照亮格子，不会点亮一排灯。如果直接模拟亮灯，时空不允许。因为照亮的是一排，考虑对所有横排竖排斜排编号，维护这些排上的亮灯个数。查询某个格子时，如果经过这个格子的所有横排竖排斜排上没有亮灯，查询答案即为没被照亮。对于灭灯操作，考虑维护一个亮灯集合，用于查询该位置及其周围是否有亮灯，如果有删除位置并修改对应排上的亮灯个数。

对于排的编号，行列可以用下标编号。对角线可以用下标之差或下标之和编号，因为某一对角线排上所有格子下标差是定值。反对角线同理，和是定值。

代码

class Solution {
public:
    vector<int> gridIllumination(int n, vector<vector<int>>& lamps, vector<vector<int>>& queries) {
        using pii = pair<int, int>;
        unordered_map<int, int> col_cnt, row_cnt, dia_cnt, adia_cnt;
        auto hash_p = [](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<pii, decltype(hash_p)> lamp_xy(0, hash_p);

        for (auto lamp : lamps)
        {
            int x = lamp[0], y = lamp[1];
            if (lamp_xy.count({x, y}) > 0) continue;

            col_cnt[y]++;
            row_cnt[x]++;
            dia_cnt[x - y]++;
            adia_cnt[x + y]++;

            lamp_xy.insert({x, y});
        }

        cout << row_cnt[0];

        vector<int> ans;
        for (auto query : queries)
        {
            int x = query[0], y = query[1];
            if ((col_cnt.count(y) > 0 && col_cnt[y] > 0) || 
                (row_cnt.count(x) > 0 && row_cnt[x] > 0) ||
                (dia_cnt.count(x - y) > 0 && dia_cnt[x - y] > 0) ||
                adia_cnt.count(x + y) > 0 && adia_cnt[x + y] > 0)
            {
                ans.push_back(1);
            }
            else
            {
                ans.push_back(0);
            }

            for (int nx = x - 1; nx <= x + 1; nx++)
            {
                for (int ny = y - 1; ny <= y + 1; ny++)
                {
                    if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
                    auto iter = lamp_xy.find({nx, ny});
                    if (iter != lamp_xy.end()) 
                    {
                        lamp_xy.erase(iter);

                        col_cnt[ny]--;
                        row_cnt[nx]--;
                        dia_cnt[nx - ny]--;
                        adia_cnt[nx + ny]--;                       
                    }
                }
            }
        }
        return ans;
    }
};