1001. Grid Illumination

You are given a `grid` of size `N x N`, and each cell of this grid has a lamp that is initially turned off.

You are also given an array of lamp positions `lamps`, where `lamps[i] = [rowi, coli]` indicates that the lamp at `grid[rowi][coli]` is turned on. When a lamp is turned on, it illuminates its cell and all other cells in the same row, column, or diagonal.

Finally, you are given a query array `queries`, where `queries[i] = [rowi, coli]`. For the `ith` query, determine whether `grid[rowi][coli]` is illuminated or not. After answering the `ith` query, turn off the lamp at `grid[rowi][coli]` and its 8 adjacent lamps if they exist. A lamp is adjacent if its cell shares either a side or corner with `grid[rowi][coli]`.

Return  an array of integers `ans` ,* where  `ans[i]`  should be  `1`  if the lamp in the  `ith`  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`
• `lamps[i].length == 2`
• `0 <= lamps[i][j] < N`
• `0 <= queries.length <= 20000`
• `queries[i].length == 2`
• `0 <= queries[i][j] < N`

``````class Solution {
public:
vector<int> gridIllumination(int N, vector<vector<int>>& lamps, vector<vector<int>>& queries) {
vector<int> res(queries.size());
vector<vector<int>> dirs{{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}, {0, 0}};
unordered_map<int, int> rowMap, colMap, diagMap, invDiagMap;
set<vector<int>> lampSet;
for (auto &lamp : lamps) {
++rowMap[lamp[0]];
++colMap[lamp[1]];
++diagMap[lamp[0] - lamp[1]];
++invDiagMap[lamp[0] + lamp[1]];
lampSet.insert({lamp[0], lamp[1]});
}
for (int i = 0; i < queries.size(); ++i) {
int x0 = queries[i][0], y0 = queries[i][1];
if (rowMap[x0] > 0 || colMap[y0] > 0 || diagMap[x0 - y0] > 0 || invDiagMap[x0 + y0] > 0) {
res[i] = 1;
}
for (auto &dir : dirs) {
int x = x0 + dir[0], y = y0 + dir[1];
if (lampSet.count({x, y})) {
--rowMap[x];
--colMap[y];
--diagMap[x - y];
--invDiagMap[x + y];
lampSet.erase({x, y});
}
}
}
return res;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1001

N-Queens

N-Queens II

https://leetcode.com/problems/grid-illumination/

https://leetcode.com/problems/grid-illumination/discuss/242898/C%2B%2B-with-picture-similar-to-N-Queens

https://leetcode.com/problems/grid-illumination/discuss/243076/Java-Clean-Code-O(N)-Time-and-O(N)-Space-Beats-100

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation