Problem

On a N x N grid of cells, each cell (x, y) with 0 <= x < N and 0 <= y < N has a lamp.

Initially, some number of lamps are on. lamps[i] tells us the location of the i-th lamp that is on. Each lamp that is on illuminates every square on its x-axis, y-axis, and both diagonals (similar to a Queen in chess).

For the i-th query queries[i] = (x, y), the answer to the query is 1 if the cell (x, y) is illuminated, else 0.

After each query (x, y) [in the order given by queries], we turn off any lamps that are at cell (x, y) or are adjacent 8-directionally (ie., share a corner or edge with cell (x, y).)

Return an array of answers. Each value answer[i] should be equal to the answer of the i-th query queries[i].

Example 1:

Input: N = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]]
Output: [1,0]
Explanation: 
Before performing the first query we have both lamps [0,0] and [4,4] on.
The grid representing which cells are lit looks like this, where [0,0] is the top left corner, and [4,4] is the bottom right corner:
1 1 1 1 1
1 1 0 0 1
1 0 1 0 1
1 0 0 1 1
1 1 1 1 1
Then the query at [1, 1] returns 1 because the cell is lit.  After this query, the lamp at [0, 0] turns off, and the grid now looks like this:
1 0 0 0 1
0 1 0 0 1
0 0 1 0 1
0 0 0 1 1
1 1 1 1 1
Before performing the second query we have only the lamp [4,4] on.  Now the query at [1,0] returns 0, because the cell is no longer lit.

Note:

1 <= N <= 10^9
0 <= lamps.length <= 20000
0 <= queries.length <= 20000
lamps[i].length == queries[i].length == 2

思路

问题核心是找到 query 是不是处在 lamps 能照亮的路径上。我的思路比较直觉，即把这个命题转换一下，只要从 query 出发的 8 个方向上存在 lamp，就说明被照亮。类似 nvidia 的 ray tracing （大嘘

Solution

class Solution(object):
    def backTracing(self, N, lamps, query, offset):    # recursively trace back
        i, j = query
        oi, oj = offset
        ci, cj = current = (i + oi, j + oj)
        if not (0 <= ci < N and 0 <= cj < N):
            return False

        if current in lamps:
            return True
        elif current == query:
            return query in lamps
        return self.backTracing(N, lamps, current, offset)


    def turnOff(self, N, lamps, query):
        for i in range(query[0] - 1, query[0] + 2):
            for j in range(query[1] - 1, query[1] + 2):
                if (i, j) in lamps:
                    lamps.remove((i ,j))
        return lamps

    def gridIllumination(self, N, lamps, queries):
        """
        :type N: int
        :type lamps: List[List[int]]
        :type queries: List[List[int]]
        :rtype: List[int]
        """
        res = []
        lamps = {(lamp[0], lamp[1]) for lamp in lamps}

        for i, query in enumerate(queries):
            res.append(int(self.backTracing(N, lamps, query, (-1, 0)) or \
                            self.backTracing(N, lamps, query, (-1, -1)) or \
                            self.backTracing(N, lamps, query, (-1, 1)) or \
                            self.backTracing(N, lamps, query, (0, -1)) or \
                            self.backTracing(N, lamps, query, (0, 0)) or \
                            self.backTracing(N, lamps, query, (0, 1)) or \
                            self.backTracing(N, lamps, query, (1, -1)) or \
                            self.backTracing(N, lamps, query, (1, 0)) or \
                            self.backTracing(N, lamps, query, (1, 1))))
            lamps = self.turnOff(N, lamps, query)
        return res

看起来很完美，答案也是正确的，但可惜到 15/33 就超时了，

Conclusion

第一个不看讨论区自己撸出来的答案，还是没法提交成功，有点小失落。再接再厉把。。。

Ref

leetcode problem 1001