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

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

ตัวอย่าง: N = 5, lamps = [[0,0],[4,4]], query = [[1,1],[1,0]] → output [1,0]

ขั้นตอนการแก้ปัญหา

• สร้างเซต lamps จากอาร์เรย์ที่กำหนด
• สร้าง dictionary นับจำนวนโคมบนแต่ละแถว (x), คอลัมน์ (y), เส้นทแยงหลัก (i+j), เส้นทแยงรอง (i-j)
• วนลูปแต่ละ query: ตรวจสอบว่ามีโคมส่องสว่างหรือไม่จากจำนวนใน dictionary
• ปิดโคมในพื้นที่ 3x3 รอบ query point และอัปเดต dictionary

ตัวอย่างโค้ด

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]