LeetCode1001:网格照明问题解析

问题描述

在一个N×N的网格中，每个单元格(x, y)（其中0 ≤ x

返回一个数组，其中每个元素对应于查询的结果。

示例 1:

输入: N = 5, 灯泡位置 = [[0,0],[4,4]], 查询 = [[1,1],[1,0]]
输出: [1,0]
解释: 在第一个查询之前，灯泡位于[0,0]和[4,4]。
网格中被照亮的单元格如下所示：
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
第一次查询(1,1)返回1，因为该单元格被照亮。这次查询后，灯泡[0,0]关闭，网格变为：
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
第二次查询前，只有灯泡[4,4]亮着。查询(1,0)返回0，因为该单元格不再被照亮。

注意：

1 ≤ N ≤ 10^9
0 ≤ 灯泡数量 ≤ 20000
0 ≤ 查询数量 ≤ 20000
每个灯泡和查询的位置由两个整数表示。

解决方案分析

考虑到N的最大值为10^9，直接创建一个N×N的网格来存储所有数据是不切实际的。此外，这样的网格中会有很多不必要的0，因此需要使用更高效的数据结构来存储和处理数据。

关系分析

1. 灯泡与其照亮的单元格之间的关系是双向的，因为需要根据照亮的单元格来决定关闭哪些灯泡，同时关闭灯泡后需要熄灭其照亮的所有单元格。
2. 查询的位置与被照亮的单元格之间的关系是单向的，用于查找。
3. 查询的位置周围的8个单元格与灯泡的位置之间的关系也是单向的，因为每次查询后需要检查并关闭周围的灯泡。
4. 一个单元格可能被多个灯泡照亮，因此存在一对多的关系。

数据结构与算法流程

数据结构

为了有效地存储上述关系，可以使用以下数据结构：
1. map, int> point_frep：存储每个被照亮的单元格及其对应的灯泡数量。
2. map x_frep：存储每行被照亮的次数。
3. map y_frep：存储每列被照亮的次数。
4. map sum_frep, map diff_frep：分别存储主对角线和副对角线被照亮的次数。

关于对角线关系的说明：
当灯泡位于(0,2)时，可以观察到：
1. 被照亮的绿色单元格满足 (x + y = 2)。
2. 被照亮的红色单元格满足 (x - y = -2)。
因此，可以通过计算 (x + y) 和 (x - y) 来判断某个单元格是否被某个灯泡照亮。

算法流程

1. 遍历所有的灯泡位置，初始化上述数据结构。
2. 对于每个查询：
- 判断查询的单元格是否被照亮。
- 检查并关闭查询单元格及其周围的8个单元格中的灯泡，更新相关数据结构。

参考解决方案

以下是一个高效的C++实现，来自用户@neal_wu：

class Solution {public:vector gridIllumination(int N, vector>& lamps, vector>& queries) {int L = lamps.size(), Q = queries.size();map, int> point_frep;map x_frep, y_frep, sum_frep, diff_frep;for (auto lamp : lamps) {int x = lamp[0], y = lamp[1];point_frep[make_pair(x, y)]++;x_frep[x]++;y_frep[y]++;sum_frep[x + y]++;diff_frep[x - y]++;}vector res;for (auto query : queries) {int x = query[0], y = query[1];bool ans = x_frep[x] > 0 || y_frep[y] > 0 || sum_frep[x + y] > 0 || diff_frep[x - y] > 0;res.push_back(ans ? 1 : 0);for (int dx = -1; dx <= 1; ++dx) {for (int dy = -1; dy <= 1; ++dy) {int nx = x + dx, ny = y + dy;int freq = point_frep[make_pair(nx, ny)];if (freq > 0) {x_frep[nx] -= freq;y_frep[ny] -= freq;sum_frep[nx + ny] -= freq;diff_frep[nx - ny] -= freq;point_frep[make_pair(nx, ny)] -= freq;}}}}return res;}}