1001.网格照明

链接：1001.网格照明
难度：Hard
标签：数组、哈希表
简介：在大小为 n x n 的网格 grid 上，每个单元格都有一盏灯，最初灯都处于 关闭 状态。返回一个整数数组 ans 作为答案， ans[j] 应等于第 j 次查询 queries[j] 的结果，1 表示照亮，0 表示未照亮。

题解 1 - cpp

• 编辑时间：2022-02-08
• 执行用时：644ms
• 内存消耗：178.3MB
• 编程语言：cpp
• 解法介绍：哈希存储每个点的行列斜线。

int dirs[9][2] = {{0, 1},  {0, -1},  {1, 0},  {-1, 0}, {1, 1},
                  {1, -1}, {-1, -1}, {-1, 1}, {0, 0}};
class Solution {
   public:
    int get_b(int x, int y, int k) { return y - x * k; }
    vector<int> gridIllumination(int n, vector<vector<int>>& lamps,
                                 vector<vector<int>>& queries) {
        unordered_map<int, unordered_set<int>> m;
        unordered_map<int, int> m_x, m_y, m_k1, m_k2;
        for (auto& item : lamps) {
            int x = item[0], y = item[1];
            if (m[x].count(y)) continue;
            m[x].insert(y);
            m_x[x]++;
            m_y[y]++;
            m_k1[get_b(x, n - y - 1, 1)]++;
            m_k2[get_b(x, n - y - 1, -1)]++;
        }
        vector<int> ans;
        for (auto& item : queries) {
            int x = item[0], y = item[1], state = 0;
            if (m_x[x] || m_y[y] || m_k1[get_b(x, n - y - 1, 1)] ||
                m_k2[get_b(x, n - y - 1, -1)])
                state = 1;
            ans.push_back(state);
            for (int i = 0; i < 9; i++) {
                int nx = x + dirs[i][0], ny = y + dirs[i][1];
                if (nx < 0 || ny < 0 || nx >= n || ny >= n || !m[nx].count(ny))
                    continue;
                m_x[nx]--;
                m_y[ny]--;
                m_k1[get_b(nx, n - ny - 1, 1)]--;
                m_k2[get_b(nx, n - ny - 1, -1)]--;
                m[nx].erase(ny);
            }
        }
        return ans;
    }
};