Python 中的网格照明
假设我们有一个 N x N 单元格网格，每个单元格 (x, y) 中都有一盏灯。最初，有些灯是亮着的。lamps[i] 是第 i 盏亮着的灯的位置。每盏亮着的灯都会在其 x 轴、y 轴和两个对角线上的每个方块发光。现在对于第 i 个查询，即 queries[i] = (x, y)，如果单元格 (x, y) 发光，则查询的答案为 1，否则为 0。每次查询 (x, y) 后，我们关闭单元格 (x, y) 或 8 个方向上相邻的所有灯。返回答案数组。每个值 answer[i] 应等于第 i 个查询 queries[i] 的答案。
因此，如果输入为 N = 5，lamps 为 [[0,0],[4,4]]，query = [[1,1],[1,0]]，则输出将为 [1,0]
为了解决这个问题，我们将遵循以下步骤 −
lamps := 给定数组 lamps 中的对集
创建映射 x、y、diag1、diag2
对于 lamps 中的每一对 (i, j)
x[i] := x[i] + 1，y[j] := y[j] + 1
diag1[i + j] := diag1[i + j] + 1, diag2[i - j] = diag2[i - j] + 1
ans := []
对于 C 中的每个值 i
a := i[0], b := i[1]
将 (1 if x[a] + y[b] + diag1[a + b] + diag2[a - b] > 0 else 0) 插入 ans
对于 a - 1 到 a + 1 范围内的行
对于 b - 1 到 b + 1 范围内的列
如果行、列对在灯，然后 −
x[row] := x[row] - 1
y[col] := y[col] - 1
diag1[row + col] = diag1[row + col] - 1
diag2[row - col] = diag2[row - col] - 1
从灯中删除(row，col)
返回 ans
让我们看看下面的实现以便更好地理解 −
示例
from collections import defaultdict
class Solution(object):
def gridIllumination(self, N, b, C):
lamps = {(i[0], i[1]) for i in b}
x, y, diag1, diag2 = defaultdict(int), defaultdict(int),
defaultdict(int), defaultdict(int)
for i, j in lamps:
x[i] += 1
y[j] += 1
diag1[i + j] += 1
diag2[i - j] += 1
ans = []
for i in C:
a = i[0]
b = i[1]
ans.append(1 if x[a] + y[b] + diag1[a + b] + diag2[a - b] > 0 else 0)
for row in range( a - 1, a + 2):
for col in range(b - 1, b + 2):
if (row, col) in lamps:
x[row] -= 1
y[col] -= 1
diag1[row + col] -= 1
diag2[row - col] -= 1
lamps.remove((row, col))
return ans
ob = Solution()
N = 5
lamps = [[0,0],[4,4]]
query = [[1,1],[1,0]]
print(ob.gridIllumination(N, lamps, query))
输入
5, [[0,0],[4,4]], [[1,1],[1,0]]
输出
[1, 0]
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/
