网格照明

标签: 数组 哈希表

难度: Hard

在大小为 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 表示未照亮。

示例 1：

输入：n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]]
输出：[1,0]
解释：最初所有灯都是关闭的。在执行查询之前，打开位于 [0, 0] 和 [4, 4] 的灯。第 0 次查询检查 grid[1][1] 是否被照亮（蓝色方框）。该单元格被照亮，所以 ans[0] = 1 。然后，关闭红色方框中的所有灯。

第 1 次查询检查 grid[1][0] 是否被照亮（蓝色方框）。该单元格没有被照亮，所以 ans[1] = 0 。然后，关闭红色矩形中的所有灯。

示例 2：

输入：n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,1]]
输出：[1,1]

示例 3：

输入：n = 5, lamps = [[0,0],[0,4]], queries = [[0,4],[0,1],[1,4]]
输出：[1,1,0]

提示：

  • 1 <= n <= 109
  • 0 <= lamps.length <= 20000
  • 0 <= queries.length <= 20000
  • lamps[i].length == 2
  • 0 <= rowi, coli < n
  • queries[j].length == 2
  • 0 <= rowj, colj < n

Submission

运行时间: 173 ms

内存: 36.2 MB

class Solution:
    def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:
        # Step 1: Create a set of tuples to store lamp positions
        lamp_set = set(map(tuple, lamps))
        
        # Step 2: Create dictionaries to store lamp positions
        rows = defaultdict(int)
        cols = defaultdict(int)
        diag1 = defaultdict(int)  # Diagonal from top-left to bottom-right
        diag2 = defaultdict(int)  # Diagonal from top-right to bottom-left
        
        # Step 3: Update dictionaries with lamp positions
        for row, col in lamp_set:
            rows[row] += 1
            cols[col] += 1
            diag1[row - col] += 1
            diag2[row + col] += 1
        
        # Step 4: Initialize result list and iterate over queries
        result = []
        directions = [(0, 0), (0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
        for row, col in queries:
            # Step 5: Check if the position is illuminated
            if rows[row] > 0 or cols[col] > 0 or diag1[row - col] > 0 or diag2[row + col] > 0:
                result.append(1)
                
                # Step 6: Turn off adjacent lamps
                for dx, dy in directions:
                    adj_row, adj_col = row + dx, col + dy
                    if (adj_row, adj_col) in lamp_set:
                        lamp_set.remove((adj_row, adj_col))
                        rows[adj_row] -= 1
                        if rows[adj_row] == 0:
                            del rows[adj_row]
                        cols[adj_col] -= 1
                        if cols[adj_col] == 0:
                            del cols[adj_col]
                        diag1[adj_row - adj_col] -= 1
                        if diag1[adj_row - adj_col] == 0:
                            del diag1[adj_row - adj_col]
                        diag2[adj_row + adj_col] -= 1
                        if diag2[adj_row + adj_col] == 0:
                            del diag2[adj_row + adj_col]
            else:
                # Step 7: Position is not illuminated
                result.append(0)
        
        return result

from collections import defaultdict

solution = Solution()

print(solution.gridIllumination(5, [[0,0],[4,4]], [[1,1],[1,0]]))  # Output: [1, 0]
print(solution.gridIllumination(5, [[0,0],[4,4]], [[1,1],[1,1]]))  # Output: [1, 1]
print(solution.gridIllumination(5, [[0,0],[0,4]], [[0,4],[0,1],[1,4]]))  # Output: [1, 1, 0]

Explain

该题解使用了字典来存储灯的位置信息，通过记录每一行、每一列以及两个对角线上灯的数量，可以快速判断某个位置是否被照亮。对于每个查询，先判断该位置是否被照亮，如果被照亮则将结果记为1，并关闭该位置及其相邻8个方向上的灯；如果未被照亮则将结果记为0。最后返回所有查询的结果。

时间复杂度: O(m+n)

空间复杂度: O(m)

class Solution:
    def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:
        # Step 1: Create a set of tuples to store lamp positions
        lamp_set = set(map(tuple, lamps))
        
        # Step 2: Create dictionaries to store lamp counts in each row, column, and diagonal
        rows = defaultdict(int)
        cols = defaultdict(int)
        diag1 = defaultdict(int)  # Diagonal from top-left to bottom-right
        diag2 = defaultdict(int)  # Diagonal from top-right to bottom-left
        
        # Step 3: Update dictionaries with lamp positions
        for row, col in lamp_set:
            rows[row] += 1
            cols[col] += 1
            diag1[row - col] += 1
            diag2[row + col] += 1
        
        # Step 4: Initialize result list and iterate over queries
        result = []
        directions = [(0, 0), (0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
        for row, col in queries:
            # Step 5: Check if the position is illuminated
            if rows[row] > 0 or cols[col] > 0 or diag1[row - col] > 0 or diag2[row + col] > 0:
                result.append(1)
                
                # Step 6: Turn off adjacent lamps
                for dx, dy in directions:
                    adj_row, adj_col = row + dx, col + dy
                    if (adj_row, adj_col) in lamp_set:
                        lamp_set.remove((adj_row, adj_col))
                        rows[adj_row] -= 1
                        if rows[adj_row] == 0:
                            del rows[adj_row]
                        cols[adj_col] -= 1
                        if cols[adj_col] == 0:
                            del cols[adj_col]
                        diag1[adj_row - adj_col] -= 1
                        if diag1[adj_row - adj_col] == 0:
                            del diag1[adj_row - adj_col]
                        diag2[adj_row + adj_col] -= 1
                        if diag2[adj_row + adj_col] == 0:
                            del diag2[adj_row + adj_col]
            else:
                # Step 7: Position is not illuminated
                result.append(0)
        
        return result

Explore

在算法中，每当一个灯被关闭时，该灯对应的行、列及两个对角线的计数器都会相应减少。如果这个灯是该行、列或对角线上的最后一个灯，则相关的字典项会被删除（计数器归零时）。这种方式确保了每次查询时，字典中存储的灯数量信息始终是准确的，即使经过多次关闭操作。通过这种方法，可以有效跟踪并更新每个区域的灯的实时数量。

算法中使用了一个集合（set）来存储所有的灯位置。当进行关闭操作时，会检查目标位置是否仍在集合中，如果在，则进行关闭操作并从集合中移除该灯。因此，即使一个灯位置被多次标记为关闭，由于它在第一次关闭后已经从集合中被移除，后续的关闭操作将不会再次执行。这样就避免了重复关闭的风险。

在该算法中，一个位置是否被照亮，取决于它所在的行、列或对角线上是否有灯存在。由于灯具有照亮整行、整列以及对应对角线的能力，因此仅需检查这些集合的计数器是否大于零。这样的检查方法既简化了判断流程，也加快了运行速度，因为比起遍历具体的灯位置，访问和更新计数器更为高效和快速。

在该算法中，每个行、列或对角线的计数器代表了该区域内灯的总数量。因此，即使多个灯照亮同一行或列，关闭一个灯时仅将该行或列的计数器减1是足够的。这确保了只有当该行或列的所有灯都被关闭时，计数器才会归零，从而正确反映了该行或列的照明状态。这种方法有效地维护了每个区域的照明情况，避免了错误关闭或错误照明的情况。