1001. Grid Illumination

题目信息

题号:

1001

难度:

Hard

主题:

网格、灯光状态、查询模拟

原题:

LeetCode 1001

重点:

一盏灯照亮同行、同列及两条对角线;每次查询先判断照明状态,再关闭查询格及周围八格中的所有灯

题目重述

给定一个 n x n 网格,行列下标均从 0 到 n - 1。数组 lamps 给出初始打开的灯坐标;同一坐标即使重复出现,也只表示一盏打开的灯。打开的灯会照亮自身所在的整行、整列以及两条对角线。

依次处理 queries 中的坐标。对于每次查询,先判断该格在关灯前是否被至少一盏灯照亮,并记录 1 或 0;随后关闭以查询格为中心的九宫格范围内所有仍亮着的灯,超出网格的坐标忽略。返回所有查询结果组成的数组。

1 <= n <= 10^9,0 <= lamps.length, queries.length <= 2 * 10^4,每个灯和查询坐标都包含两个整数,并且均位于网格内。

自建示例

查询后的关灯会影响后续结果:

输入:n = 5, lamps = [[0,1],[4,4]], queries = [[1,1],[3,3],[0,4]]
输出:[1,1,0]
解释:第一次查询被同列灯 [0,1] 照亮,随后该灯位于查询格九宫格内而被关闭;第二次查询被 [4,4] 的对角线照亮,并关闭该灯;第三次查询时已经没有亮灯,因此返回 0。

重复坐标只表示一盏灯:

输入:n = 3, lamps = [[1,1],[1,1]], queries = [[0,0],[2,2]]
输出:[1,0]
解释:第一次查询由灯 [1,1] 沿对角线照亮,并在查询后关闭该灯。重复坐标没有创建第二盏灯,因此第二次查询不再被照亮。