Chiếu sáng lưới trong Python

Giả sử chúng ta có lưới N x N, tại mỗi ô (x, y) có một đèn. Ban đầu, một số đèn đang bật. lamps[i] là vị trí của đèn thứ i đang bật. Mỗi đèn bật sẽ chiếu sáng mọi ô trên trục x, trục y và cả hai đường chéo của nó. Với truy vấn thứ i là queries[i] = (x, y), câu trả lời là 1 nếu ô (x, y) được chiếu sáng, ngược lại là 0. Sau mỗi truy vấn (x, y), chúng ta tắt tất cả đèn ở ô (x, y) hoặc liền kề 8 hướng. Trả về mảng các câu trả lời.

Ví dụ: N = 5, lamps = [[0,0],[4,4]], query = [[1,1],[1,0]], kết quả sẽ là [1,0].

Các bước giải quyết:

• lamps := tập hợp các cặp từ mảng lamps cho trước
• Tạo các map x, y, diag1, diag2
• Với mỗi cặp (i, j) trong lamps: tăng x[i], y[j], diag1[i+j], diag2[i-j]
• ans := mảng rỗng
• Với mỗi truy vấn i trong C: kiểm tra tổng chiếu sáng tại (a,b), thêm 1 hoặc 0 vào ans
• Tắt đèn trong phạm vi 3x3 quanh (a,b): giảm các counter và xóa khỏi lamps
• Trả về ans

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]