Pythonでのグリッドイルミネーション

セルのNxNグリッドがあり、各セル（x、y）にランプがあるとします。最初は、いくつかのランプが点灯しています。ランプ[i]は、点灯しているi番目のランプの位置です。オンになっている各ランプは、x軸、y軸、および両方の対角線上ですべての正方形を照らします。ここで、i番目のクエリ（つまり、querys [i] =（x、y））の場合、セル（x、y）が光っている場合、クエリに対する答えは1です。それ以外の場合は、0です。各クエリ（x、y）の後、セル（x、y）にあるか、8方向に隣接しているランプをすべてオフにします。回答の配列を返します。各値answer[i]は、i番目のクエリクエリ[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

• ans：=[]

• Cの値iごとに

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

  • （x [a] + y [b] + diag1 [a + b] + diag2 [a --b]> 0の場合は1、それ以外の場合は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

        • ランプから（行、列）を削除します

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