菜鸟的每日力扣系列——1001. 网格照明（#Day32）

from collections import defaultdict
from typing import List


def gridIllumination(n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:
    rows = defaultdict(int)  # 行
    cols = defaultdict(int)  # 列
    mdiags = defaultdict(int)  # 主对角线
    vdiags = defaultdict(int)  # 副对角线
    res = []  # 结果
    # 检查某位置点灯状态
    def check(x, y):
        # 分别判断行、列、主对角线、副对角线是否有灯可以照亮当前单元格
        return 1 if rows[x] > 0 or cols[y] > 0 or mdiags[x - y] > 0 or vdiags[x + y] > 0 else 0
    lamps = {(row, col) for row, col in lamps}  # 换用集合存放点灯所在行和列
    for row, col in lamps:  # 点亮行、列、主对角线、副对角线加一
        rows[row] += 1
        cols[col] += 1
        mdiags[row - col] += 1
        vdiags[row + col] += 1
    for i, j in queries:  # 查询点灯情况，并熄灭8个方向内所有灯
        x = check(i, j)
        res.append(x)  # 将结果放入数组
        if x:  # 如果找到点灯位置
            for row in range(i-1, i+2):
                for col in range(j-1, j+2):
                    if 0 <= row < n and 0 <= col < n and (row, col) in lamps:  # 在限制边界中在点灯位置中找到该点对应行列
                        lamps.remove((row, col))  # 熄灭灯，并将行、列、主对角线、副对角线减一
                        rows[row] -= 1
                        cols[col] -= 1
                        mdiags[row - col] -= 1
                        vdiags[row + col] -= 1
    return res


n = 6
lamps = [[2, 5], [4, 2], [0, 3], [0, 5], [1, 4], [4, 2], [3, 3], [1, 0]]
queries = [[4, 3], [3, 1], [5, 3], [0, 5], [4, 4], [3, 3]]
print(gridIllumination(n, lamps, queries))  # [1, 0, 1, 1, 0, 1]