题目：
在大小为 n x n 的网格 grid 上，每个单元格都有一盏灯，最初灯都处于 关闭 状态。

给你一个由灯的位置组成的二维数组 lamps ，其中 lamps[i] = [rowi, coli] 表示 打开 位于 grid[rowi][coli] 的灯。即便同一盏灯可能在 lamps 中多次列出，不会影响这盏灯处于 打开 状态。

当一盏灯处于打开状态，它将会照亮 自身所在单元格 以及同一 行 、同一 列 和两条 对角线 上的 所有其他单元格 。

另给你一个二维数组 queries ，其中 queries[j] = [rowj, colj] 。对于第 j 个查询，如果单元格 [rowj, colj] 是被照亮的，则查询结果为 1 ，否则为 0 。在第 j 次查询之后 [按照查询的顺序] ，关闭 位于单元格 grid[rowj][colj] 上及相邻 8 个方向上（与单元格 grid[rowi][coli] 共享角或边）的任何灯。

返回一个整数数组 ans 作为答案， ans[j] 应等于第 j 次查询 queries[j] 的结果，1 表示照亮，0 表示未照亮。




解答：
方法一：超时

class Solution:
    def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:
        #grid[i][j]:(i,j)被几个灯照亮着
        grid=[[0]*n for _ in range(n)]
        #单元格相邻的八个方向
        directions=[[0,0],[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]]
        #closed[i]=0：表示该处的灯未关闭
        m=len(lamps)
        closed=[0]*m
        def InArea(i,j):
            if 0<=i<n and 0<=j<n:
                return True
            return False


        #点亮或关闭灯泡(点亮flag=1,关闭flag=-1)
        def openOrSshut(i,j,flag):
            #点亮(i,j)及其同行，同列
            grid[i][j]+=flag
            for t in range(0,n):
                if t!=j:
                    grid[i][t]+=flag
                if t!=i:
                    grid[t][j]+=flag
            #点亮(i,j)所在主,副对角线
            for t in range(1,n):
                #往左上角延申
                if InArea(i-t,j-t):
                    grid[i-t][j-t]+=flag
                #往右上角延申
                if InArea(i-t,j+t):
                    grid[i-t][j+t]+=flag
                #往左下角延申
                if InArea(i+t,j-t):
                    grid[i+t][j-t]+=flag
                #往右下角延申
                if InArea(i+t,j+t):
                    grid[i+t][j+t]+=flag
            
         #点亮灯泡
        lamps.sort()
        #print(lamps)
        for t in range(m):
            if t!=0 and lamps[t]==lamps[t-1]:
                continue
            i,j=lamps[t]
            openOrSshut(i,j,1)
     

        #bfs:关闭(i,j)及相邻八个方向上的灯
        def bfs(i,j):
            for dx,dy in directions:
                if InArea(i+dx,j+dy):
                    #若当前位置有灯，且其未关闭则将其关闭
                    if [i+dx,j+dy] in lamps:
                        idx=lamps.index([i+dx,j+dy])
                        if closed[idx]==0:
                            openOrSshut(i+dx,j+dy,-1)
                            closed[idx]=1
                    #print(i+dx,j+dy,grid)
        res=[]
        #查询(i,j)是否被照亮
        for i,j in queries:
            if grid[i][j]>0:
                res.append(1)
            else:
                res.append(0)
            #关闭位于单元格8个方向上的灯,如果有灯，则将其关闭，对应被照亮的地方，
            #如果不位于其他灯的照亮范围内，则其将不被照亮
            bfs(i,j) 
            #print(grid)
     
        return res

方法二：超出时间限制

class Solution:
    def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:
        #单元格及其相邻的八个方向
        directions=[[0,0],[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]]
        #closed[i]=0：表示该处的灯未关闭
        m=len(lamps)
        closed=[0]*m
        lamps.sort()
        
        def InArea(i,j):
            if 0<=i<n and 0<=j<n:
                return True
            return False   

        #bfs:关闭(i,j)及相邻八个方向上的灯
        def bfs(i,j):
            for dx,dy in directions:
                if InArea(i+dx,j+dy):
                    #若当前位置有灯，且其未关闭则将其关闭
                    if [i+dx,j+dy] in lamps:
                        idx=lamps.index([i+dx,j+dy])
                        #同一个灯可能出现多次
                        while idx<m and lamps[idx]==[i+dx,j+dy] and closed[idx]==0:
                            closed[idx]=1
                            idx+=1

    
        res=[]        
        #查询(x,y)是否被照亮，判断其是否位于其中某栈灯的照明范围内
        for x,y in queries:
            flag=0
            #判断(x,y)是否位于某一灯泡的照明范围内
            for i,(px,py) in enumerate(lamps):
                if closed[i]!=0:
                    continue
                if px==x:
                    flag=1
                    break
                if py==y:
                    flag=1
                    break
                if px-x==py-y:
                    flag=1
                    break
                if px-x==y-py:
                    flag=1
                    break
            if flag:
                res.append(1)
            else:
                res.append(0)  
            #关闭位于单元格8个方向上的灯,如果有灯，则将其关闭，对应被照亮的地方，
            #如果不位于其他灯的照亮范围内，则其将被熄灭
            bfs(x,y)
        
        return res

方法三：

class Solution:
    def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:
        #单元格及其相邻的八个方向
        directions=[[0,0],[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]]        
        def InArea(i,j):
            if 0<=i<n and 0<=j<n:
                return True
            return False   
        
        #遍历lamps(需去重）,记录行列，主副对角线上灯的数量
        points = set()
        row, col, diagonal, antiDiagonal = Counter(), Counter(), Counter(), Counter()
        for x,y in lamps:
            if (x,y) in points:
                continue
            points.add((x,y))
            row[x]+=1
            col[y]+=1
            diagonal[x-y]+=1
            antiDiagonal[x+y]+=1


        #bfs:关闭(i,j)及相邻八个方向上的灯
        def bfs(i,j):
            for dx,dy in directions:
                x=i+dx
                y=j+dy
                if InArea(x,y):
                    #若当前位置有灯，且其未关闭则将其关闭
                    if (x,y) in points:
                        points.remove((x,y))
                        row[x]-=1
                        col[y]-=1
                        diagonal[x-y]-=1
                        antiDiagonal[x+y]-=1
        
        m=len(queries)
        res=[0]*m        
        #查询(x,y)是否被照亮，判断其是否位于其中某栈灯的照明范围内
        for i,(x,y) in enumerate(queries):
            #判断(x,y)是否位于某一灯泡的照明范围内
            if row[x] or col[y] or diagonal[x-y] or antiDiagonal[x+y]:
                res[i]=1  
            #关闭位于单元格8个方向上的灯,如果有灯，则将其关闭，对应被照亮的地方，
            #如果不位于其他灯的照亮范围内，则其将被熄灭
            bfs(x,y)
        
        return res