1001

1001. Grid Illumination (Hard)

There is a 2D grid of size n x n where each cell of this grid has a lamp that is initially turned off.

You are given a 2D array of lamp positions lamps, where lamps[i] = [rowi, coli] indicates that the lamp at grid[rowi][coli] is turned on. Even if the same lamp is listed more than once, it is turned on.

When a lamp is turned on, it illuminates its cell and all other cells in the same row, column, or diagonal.

You are also given another 2D array queries, where queries[j] = [rowj, colj]. For the jth query, determine whether grid[rowj][colj] is illuminated or not. After answering the jth query, turn off the lamp at grid[rowj][colj] and its 8 adjacent lamps if they exist. A lamp is adjacent if its cell shares either a side or corner with grid[rowj][colj].

Return an array of integers ans, where ans[j] should be 1 if the cell in the jth query was illuminated, or 0 if the lamp was not.

 

Example 1:

Input: n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]]
Output: [1,0]
Explanation: We have the initial grid with all lamps turned off. In the above picture we see the grid after turning on the lamp at grid[0][0] then turning on the lamp at grid[4][4].
The 0th query asks if the lamp at grid[1][1] is illuminated or not (the blue square). It is illuminated, so set ans[0] = 1. Then, we turn off all lamps in the red square.

The 1st query asks if the lamp at grid[1][0] is illuminated or not (the blue square). It is not illuminated, so set ans[1] = 0. Then, we turn off all lamps in the red rectangle.

Example 2:

Input: n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,1]]
Output: [1,1]

Example 3:

Input: n = 5, lamps = [[0,0],[0,4]], queries = [[0,4],[0,1],[1,4]]
Output: [1,1,0]

 

Constraints:

• 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

Companies:
Dropbox

Related Topics:
Array, Hash Table

Similar Questions:

• N-Queens (Hard)

Solution 1.

// OJ: https://leetcode.com/problems/grid-illumination/
// Author: github.com/lzl124631x
// Time: O(MlogN) where M is the length of `A`.
// Space: O(M)
class Solution {
    int getSize(unordered_map<int, set<pair<int, int>>> &m, int key) {
        return m.count(key) ? m[key].size() : 0;
    }
    void erase(unordered_map<int, set<pair<int, int>>> &m, int key, pair<int, int> val) {
        m[key].erase(val);
        if (m[key].empty()) m.erase(key);
    }
public:
    vector<int> gridIllumination(int n, vector<vector<int>>& A, vector<vector<int>>& Q) {
        vector<int> ans;
        unordered_map<int, set<pair<int, int>>> row, col, hill, dale;
        for (auto &v : A) {
            int x = v[0], y = v[1];
            if (row.count(x) && row[x].count({ x, y })) continue;
            row[x].emplace(x, y);
            col[y].emplace(x, y);
            hill[x + y].emplace(x, y);
            dale[x + n - 1 - y].emplace(x, y);
        }
        for (auto &q : Q) {
            int x = q[0], y = q[1];
            ans.push_back(getSize(row, x) + getSize(col, y) + getSize(hill, x + y) + getSize(dale, x + n - 1 - y) > 0);
            for (int dx = -1; dx <= 1; ++dx) {
                for (int dy = -1; dy <= 1; ++dy) {
                    int a = x + dx, b = y + dy;
                    if (a < 0 || a >= n || b < 0 || b >= n || row.count(a) == 0 || row[a].count({ a, b }) == 0) continue;
                    erase(row, a, {a, b});
                    erase(col, b, {a, b});
                    erase(hill, a + b, {a, b});
                    erase(dale, a + n - 1 - b, {a, b});
                }
            }
        }
        return ans;
    }
};