# LeetCode: 1001. 网格照明¶

## 1、题目描述¶

N x N 的网格上，每个单元格 (x, y) 上都有一盏灯，其中 0 <= x < N 且 0 <= y < N

输入：N = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]]

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 0 0 0 1
0 1 0 0 1
0 0 1 0 1
0 0 0 1 1
1 1 1 1 1



• 1 <= N <= 10^9
• 0 <= lamps.length <= 20000
• 0 <= queries.length <= 20000
• lamps[i].length == queries[i].length == 2

## 2、解题思路¶

• 本题目关键点在于横纵坐标与对角线的判定

temp_di = (xd * N + yd) % (N + 1) + (0 if yd >= xd else N)


temp_bdi = xd + yd

• 一开始将一开始亮的灯的横纵与对角线标号对应的引用值加1
• 等到判定的时候，将该点周围的9个点（包括自身），判断是否亮灯，亮的话，就将对应的引用值减一即可
class Solution:
def gridIllumination(self, N: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:
from collections import defaultdict
res = []
row = defaultdict(int)
col = defaultdict(int)
diagonal = defaultdict(int)
back_diagonal = defaultdict(int)

# 坐标
surround = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 0), (0, 1), (1, -1), (1, 0), (1, 1)]

# 坐标验证
def available(m, n):
return 0 <= m < N and 0 <= n < N

lamps_set = set()

for x, y in lamps:
row[x] += 1
col[y] += 1
# 对角线
di = (x * N + y) % (N + 1) + (0 if y >= x else N)
diagonal[di] += 1
# 反对角线
bdi = x + y
back_diagonal[bdi] += 1

for x, y in queries:
di = (x * N + y) % (N + 1) + (0 if y >= x else N)
bdi = x + y
if row[x] > 0 or col[y] > 0 or diagonal[di] > 0 or back_diagonal[bdi] > 0:
res.append(1)
else:
res.append(0)

for dx, dy in surround:
xd, yd = x + dx, y + dy
if available(xd, yd):
if (xd, yd) in lamps_set:
lamps_set.remove((xd, yd))
temp_di = (xd * N + yd) % (N + 1) + (0 if yd >= xd else N)
temp_bdi = xd + yd

row[xd] -= 1
col[yd] -= 1
diagonal[temp_di] -= 1
back_diagonal[temp_bdi] -= 1
return res