LC 1001. 网格照明

题目描述

这是 LeetCode 上的 1001. 网格照明 ，难度为 困难。

在大小为 n x n 的网格 grid 上，每个单元格都有一盏灯，最初灯都处于 关闭 状态。

给你一个由灯的位置组成的二维数组 lamps，其中 $lamps[i] = [row_i, col_i]$ 表示 打开 位于 grid[rowi][coli] 的灯。即便同一盏灯可能在 lamps 中多次列出，不会影响这盏灯处于 打开 状态。

当一盏灯处于打开状态，它将会照亮 自身所在单元格 以及同一 行 、同一 列 和两条 对角线 上的 所有其他单元格 。

另给你一个二维数组 queries，其中 $queries[j] = [row_j, col_j]$ 。对于第 $j$ 个查询，如果单元格 $[row_j, col_j]$ 是被照亮的，则查询结果为 $1$ ，否则为 $0$ 。

在第 j 次查询之后 [按照查询的顺序] ，关闭 位于单元格 $grid[row_j][col_j]$ 上及相邻 $8$ 个方向上（与单元格 $grid[row_i][col_i]$ 共享角或边）的任何灯。

返回一个整数数组 ans 作为答案， ans[j] 应等于第 j 次查询 queries[j] 的结果，$1$ 表示照亮，$0$ 表示未照亮。

示例 1：

1
2
3
输入：n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]]

输出：[1,0]


1
解释：最初所有灯都是关闭的。在执行查询之前，打开位于 [0, 0] 和 [4, 4] 的灯。第 0 次查询检查 grid[1][1] 是否被照亮（蓝色方框）。该单元格被照亮，所以 ans[0] = 1 。然后，关闭红色方框中的所有灯。


1
第 1 次查询检查 grid[1][0] 是否被照亮（蓝色方框）。该单元格没有被照亮，所以 ans[1] = 0 。然后，关闭红色矩形中的所有灯。

示例 2：
1
2
3
输入：n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,1]]

输出：[1,1]

示例 3：
1
2
3
输入：n = 5, lamps = [[0,0],[0,4]], queries = [[0,4],[0,1],[1,4]]

输出：[1,1,0]

提示：

  • $1 <= n <= 10^9$
  • $0 <= lamps.length <= 20000$
  • $0 <= queries.length <= 20000$
  • $lamps[i].length == 2$
  • $0 <= row_i, col_i < n$
  • $queries[j].length == 2$
  • $0 <= row_j, col_j < n$

哈希表 + 线映射

棋盘大小的数据范围为 $n = 10^9$，硬模拟「亮灯」的操作必然会 TLE，而 lamps 和 queries 数据范围为 $20000$ 是一个较为常见的突破口。

由于点亮每一盏灯，可以使得当前 行、列 和 对角线 的位置被照亮，行列可直接使用棋盘坐标的 $(x, y)$ 来代指，而对角线则可以使用「截距」来进行代指，即使用 $x + y$ 和 $x - y$ 进行代指。

分别使用四个「哈希表」row、col、left 和 right 来记录 行、列 和 对角线 的点亮情况（key 为线编号，value 为点亮次数）。

这样我们可以在 $O(1)$ 的复杂度处理掉所有的 $lamps[i]$，某个位置被照亮的充要条件为：「当前位置所在行被点亮」或「当前位置所在列被点亮」或「当前位置所处的对角线被点亮」。

同时，由于每次查询后要进行「灭灯」操作（注意：灭灯只能灭有灯的位置，而不是灭有光的位置 🤣），因此我们还需要另外记录每个灯的位置，可以使用利用「二维转一维」的技巧进行编号：$idx = x * n + y$，并使用 HashSet 进行记录（忽略重复的 $lamps[i]$）。

由于询问次数最多为 $20000$，因此直接在查询完成后模拟「灭灯」即可（访问自身及相邻格子，共 $9$ 个），计算量为 $2 * 10^5$ 以内，可以接受。若某个位置存在灯，将其从 HashSet 中移除，并更新对应线的点亮情况。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    int[][] dirs = new int[][]{{0,0},{0,-1},{0,1},{-1,0},{-1,-1},{-1,1},{1,0},{1,-1},{1,1}};
    public int[] gridIllumination(int n, int[][] lamps, int[][] queries) {
        long N = n;
        Map<Integer, Integer> row = new HashMap<>(), col = new HashMap<>();
        Map<Integer, Integer> left = new HashMap<>(), right = new HashMap<>();
        Set<Long> set = new HashSet<>();
        for (int[] l : lamps) {
            int x = l[0], y = l[1];
            int a = x + y, b = x - y;
            if (set.contains(x * N + y)) continue;
            increment(row, x); increment(col, y);
            increment(left, a); increment(right, b);
            set.add(x * N + y);
        }
        int m = queries.length;
        int[] ans = new int[m];
        for (int i = 0; i < m; i++) {
            int[] q = queries[i];
            int x = q[0], y = q[1];
            int a = x + y, b = x - y;
            if (row.containsKey(x) || col.containsKey(y) || left.containsKey(a) || right.containsKey(b)) ans[i] = 1;

            for (int[] d : dirs) {
                int nx = x + d[0], ny = y + d[1];
                int na = nx + ny, nb = nx - ny;
                if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
                if (set.contains(nx * N + ny)) {
                    set.remove(nx * N + ny);
                    decrement(row, nx); decrement(col, ny);
                    decrement(left, na); decrement(right, nb);
                }
            }
        }
        return ans;
    }
    void increment(Map<Integer, Integer> map, int key) {
        map.put(key, map.getOrDefault(key, 0) + 1);
    }
    void decrement(Map<Integer, Integer> map, int key) {
        if (map.get(key) == 1) map.remove(key);
        else map.put(key, map.get(key) - 1);
    }
}

  • 时间复杂度：令 $lamps$ 长度为 $a$，$queries$ 长度为 $b$，处理所有的 $lamp[i]$ 复杂度为 $O(a)$，处理所有的 $queries[j]$ 复杂度为 $O(C b)$，其中 $C$ 为模拟灭灯时所联通的格子数量，固定为 $9$。整体复杂度为 $O(a + C b)$
  • 空间复杂度：$O(a)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1001 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。