Algorithm (HashMap, Simulation)
- We note that a row (or column or diagonal) could be lighted if and only if there is a light in that row (or column or diagonal).
- So it suffices for us to keep track of the positions (if any) of lights in each row, col or diagonal.
- To do so, we use 4 hash maps (one for each of row, col diagonal). We also note that
- the key or each row or col is just its row or column number.
- the key for the usual diagonal is $r-c+N-1$, this is because for two elements $M_{i_{1}j_{1}}$ and $M_{i_{2}j_{2}}$ to be on the same diagonal, it must follow that $i_{1}-j_{1}=i_{2}-j_{2}$.
- the key for the reverse diagoanl is $r+c$. This is because for two elements $M_{i_{1}j_{2}}$ and $M_{i_{2}j_{2}}$ to be on the same reverse diagoanl, it must follow that $i_{1}+j_{1}=i_{2}+j_{2}.$
- The implementation then become routine.
Code (Cpp17)
class Solution {
public:
vector<int> gridIllumination(int N, vector<vector<int>>& lamps, vector<vector<int>>& queries) {
const int dr[9] = {1, -1, 0, 0, 1, -1, 1, -1, 0};
const int dc[9] = {0, 0, 1, -1, 1, -1, -1, 1, 0};
const struct {
mutable std::unordered_map<int, std::unordered_set<int>> row;
mutable std::unordered_map<int, std::unordered_set<int>> col;
mutable std::unordered_map<int, std::unordered_set<int>> diag_l;
mutable std::unordered_map<int, std::unordered_set<int>> diag_r;
} state;
auto switch_on = [&](int r, int c) {
state.row[r].emplace(c);
state.col[c].emplace(r);
state.diag_r[r - c + N - 1].emplace(r);
state.diag_l[r + c].emplace(r);
};
auto switch_off = [&](int r, int c) {
state.row[r].erase(c);
state.col[c].erase(r);
state.diag_r[r - c + N - 1].erase(r);
state.diag_l[r + c].erase(r);
};
auto inbound = [&](int r, int c) {
return 0 <= r and r < N and 0 <= c and c < N;
};
auto query = [&](int r, int c) {
return not (std::empty(state.col[c])
and std::empty(state.row[r])
and std::empty(state.diag_r[r - c + N - 1])
and std::empty(state.diag_l[r + c]));
};
const auto solution = [&](std::vector<int> self = {}) {
// prepare initial state
for (const auto & lamp : lamps)
switch_on(lamp[0], lamp[1]);
// accumulate answer
for (const auto & q : queries) {
const auto [r, c] = pair(q[0], q[1]);
self.emplace_back(query(r, c));
for (int i = 0; i < 9; ++i)
if (inbound(r + dr[i], c + dc[i]))
switch_off(r + dr[i], c + dc[i]);
}
return self;
}();
return solution;
}
};