# 1001. Grid Illumination 网格照明

@TOC

## # 题目描述

On a `N x N` grid of cells, each cell `(x, y)` with `0 <= x < N` and `0 <= y < N` has a lamp.

Initially, some number of lamps are on. `lamps[i]` tells us the location of the i-th lamp that is on. Each lamp that is on illuminates every square on its x-axis, y-axis, and both diagonals (similar to a Queen in chess).

For the i-th query queries[i] = (x, y), the answer to the query is 1 if the cell (x, y) is illuminated, else 0.

After each query `(x, y)` [in the order given by `queries`], we turn off any lamps that are at cell `(x, y)` or are adjacent 8-directionally (ie., share a corner or edge with cell `(x, y)`.)

Return an array of answers. Each value `answer[i]` should be equal to the answer of the `i`-th query `queries[i]`.

Example 1:

``````Input: N = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]]
Output: [1,0]
Explanation:
Before performing the first query we have both lamps [0,0] and [4,4] on.
The grid representing which cells are lit looks like this, where [0,0] is the top left corner, and [4,4] is the bottom right corner:
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
Then the query at [1, 1] returns 1 because the cell is lit.  After this query, the lamp at [0, 0] turns off, and the grid now looks like this:
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
Before performing the second query we have only the lamp [4,4] on.  Now the query at [1,0] returns 0, because the cell is no longer lit.
``````

Note:

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

## # 解题方法

### # 哈希

C++代码如下：

``````class Solution {
public:
vector<int> gridIllumination(int N, vector<vector<int>>& lamps, vector<vector<int>>& queries) {
unordered_map<int, int> xcount;
unordered_map<int, int> ycount;
unordered_map<int, int> l_diagcount;
unordered_map<int, int> r_diagcount;
set<pair<int, int>> lset;
for (auto l : lamps) {
++xcount[l[0]];
++ycount[l[1]];
++l_diagcount[l[0] + l[1]];
++r_diagcount[l[0] - l[1]];
lset.insert({l[0], l[1]});
}
vector<int> res;
for (auto q : queries) {
if (xcount[q[0]] || ycount[q[1]] || l_diagcount[q[0] + q[1]] || r_diagcount[q[0] - q[1]]) {
res.push_back(1);
} else {
res.push_back(0);
}
for (int i = -1; i <= 1; ++i) {
for (int j = -1; j <= 1; ++j) {
pair<int, int> xy = {q[0] + i, q[1] + j};
if (lset.count(xy)) {
--xcount[xy.first];
--ycount[xy.second];
--l_diagcount[xy.first + xy.second];
--r_diagcount[xy.first - xy.second];
lset.erase(xy);
}
}
}
}
return res;
}
};
``````

## # 日期

2019 年 2 月 24 日 —— 周末又结束了