Chiếu sáng lưới bằng Python

Giả sử chúng ta có một lưới N x N gồm các ô, trong mỗi ô (x, y) có một đèn. Ban đầu, một số đèn được bật. Đèn [i] là vị trí của đèn thứ i được bật. Mỗi đèn được bật sẽ phát sáng mọi hình vuông trên trục x, trục y và cả hai đường chéo của nó. Bây giờ đối với truy vấn thứ i, tức là các truy vấn [i] =(x, y), câu trả lời cho truy vấn là 1 nếu ô (x, y) được phát sáng, ngược lại là 0. Sau mỗi truy vấn (x, y), chúng ta tắt bất kỳ đèn nào ở ô (x, y) hoặc gần nhau theo hướng 8. Trả lại một loạt các câu trả lời. Mỗi câu trả lời giá trị [i] phải bằng câu trả lời của các câu truy vấn thứ i [i].

Vì vậy, nếu đầu vào là N =5, đèn là [[0,0], [4,4]], query =[[1,1], [1,0]], thì đầu ra sẽ là [1 , 0]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Đèn:=tập hợp các cặp từ đèn mảng đã cho

• Tạo bản đồ x, y, Diag1, Diag2

• cho mỗi cặp (i, j) trong đèn

  • 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:=[]

• cho mỗi giá trị tôi trong C

  • a:=i [0], b:=i [1]

  • chèn (1 nếu x [a] + y [b] + Diag1 [a + b] + Diag2 [a - b]> 0 nếu không thì 0) vào ans

  • cho hàng trong phạm vi a - 1 đến a + 1

    • cho col trong phạm vi b - 1 đến b + 1

      • nếu hàng, cặp col nằm trong đèn, thì -

        • x [hàng]:=x [hàng] - 1

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

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

        • cross2 [row - col] =Diag2 [row - col] - 1

        • loại bỏ (hàng, cột) khỏi đèn

• trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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))

Đầu vào

5, [[0,0],[4,4]], [[1,1],[1,0]]

Đầu ra

[1, 0]