การส่องสว่างของกริดใน Python

สมมติว่าเรามีตารางเซลล์ N x N แต่ละเซลล์ (x, y) มีหลอดไฟ เริ่มแรกหลอดไฟบางดวงเปิดอยู่ โคมไฟ[i] คือตำแหน่งของหลอดไฟที่ i ที่เปิดอยู่ โคมไฟแต่ละดวงที่ติดสว่างทุกช่องบนแกน x แกน y และแนวทแยงทั้งสองข้าง ตอนนี้สำหรับข้อความค้นหาที่ i เช่น คำสั่ง [i] =(x, y) คำตอบสำหรับข้อความค้นหาคือ 1 หากเซลล์ (x, y) เรืองแสง มิฉะนั้น 0 หลังจากแต่ละข้อความค้นหา (x, y) เรา ปิดหลอดไฟที่อยู่เซลล์ (x, y) หรืออยู่ติดกัน 8 ทิศทาง ส่งกลับอาร์เรย์ของคำตอบ แต่ละค่า answer[i] ควรเท่ากับคำตอบของแบบสอบถาม i-th[i].

ดังนั้น หากอินพุตเป็น N =5 หลอดจะเป็น [[0,0],[4,4]], query =[[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

• ตอบ :=[]

• สำหรับแต่ละค่า i ใน C

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

  • แทรก (1 ถ้า x[a] + y[b] + diag1[a + b] + diag2[a - b]> 0 มิฉะนั้น 0) ลงใน ans

  • สำหรับแถวที่อยู่ในช่วง a - 1 ถึง a + 1

    • สำหรับ col ในช่วง b - 1 ถึง b + 1

      • ถ้าแถวคู่ col อยู่ในโคมไฟแล้ว −

        • x[row] :=x[row] - 1

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

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

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

        • ถอด (แถว col) ออกจากโคมไฟ

• กลับมาอีกครั้ง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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]