Python中的网格照明

假设我们有一个N x N的单元格，在每个单元格(x,y)中都有一个灯。最初，某些灯点亮。这些灯[i]是第i个灯点亮的位置。每个点亮的灯在其x轴，y轴和两个对角线上的每个正方形均发光。现在，对于第i个查询，即querys [i] =(x,y)，如果单元格(x,y)发光，则查询的答案为1，否则为0。在每个查询(x,y)之后，我们关闭位于单元格(x,y)或与8方向相邻的所有灯。返回答案数组。每个值answer [i]应该等于第i个查询query [i]的答案。

因此，如果输入为N = 5，则灯为[[0,0]，[4,4]]，查询= [[1,1]，[1,0]]，则输出为[1 ，0]

为了解决这个问题，我们将遵循以下步骤-

• 灯：=给定阵列灯的成对对

• 创建映射x，y，diag1，diag2

• 对于灯中的每对(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

• 回答：= []

• 对于C中的每个值

• 对于在b-1到b + 1范围内的col

• x [行]：= x [行]-1

• y [col]：= y [col]-1

• diag1 [row + col] = diag1 [row + col]-1

• diag2 [row-col] = diag2 [row-col]-1

• 从灯上移开

• 如果行，col对在灯中，则-

• a：= i [0]，b：= i [1]

• 插入（如果x [a] + y [b] + diag1 [a + b] + diag2 [a-b]> 0，否则为0，则插入1）到ans

• 适用于范围a-1至a + 1的行

• 返回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]