leetcode 2257. Count Unguarded Cells in the Grid（python）

語言: CN / TW / HK
時間 2022-05-20 12:15:25

描述

You are given two integers m and n representing a 0-indexed m x n grid. You are also given two 2D integer arrays guards and walls where guards[i] = [rowi, coli] and walls[j] = [rowj, colj] represent the positions of the ith guard and jth wall respectively. A guard can see every cell in the four cardinal directions (north, east, south, or west) starting from their position unless obstructed by a wall or another guard. A cell is guarded if there is at least one guard that can see it. Return the number of unoccupied cells that are not guarded.

Example 1:

Input: m = 4, n = 6, guards = [[0,0],[1,1],[2,3]], walls = [[0,1],[2,2],[1,4]]
Output: 7
Explanation: The guarded and unguarded cells are shown in red and green respectively in the above diagram.
There are a total of 7 unguarded cells, so we return 7.

Example 2:

Input: m = 3, n = 3, guards = [[1,1]], walls = [[0,1],[1,0],[2,1],[1,2]]
Output: 4
Explanation: The unguarded cells are shown in green in the above diagram.
There are a total of 4 unguarded cells, so we return 4.

Note:

1 <= m, n <= 10^5
2 <= m * n <= 10^5
1 <= guards.length, walls.length <= 5 * 10^4
2 <= guards.length + walls.length <= m * n
guards[i].length == walls[j].length == 2
0 <= rowi, rowj < m
0 <= coli, colj < n
All the positions in guards and walls are unique.

解析

根據題意，給定兩個整數 m 和 n ，表示一個 0 索引的 m x n 網格。 給定兩個二維整數陣列 guards 和 walls ，其中 guards[i] = [rowi, coli] 和 walls[j] = [rowj, colj] 分別代表第 i 個保安和第 j 個牆的位置。

守衛可以從他們的位置開始看到四個主要方向（北、東、南或西）的每個單元，除非被牆或其他守衛阻擋。 返回未被看守的單元格的數量。

這道題其實就是一個遍歷格子的問題，思路也比較簡單，初始化一個全都是 0 的 grid ，然後將保安和牆的格子 2 表示這些位置已經有了站位或者阻擋，然後再遍歷每個保安能看到的四個方向的格子，如果 grid[i][j] 上的數字為 0 或者 1 表示其還沒有保衛或者已經保衛，然後將 grid[i][j] 設定為 1 即可，遍歷結束只需要返回 grid 中還是 0 的格子數量即可。

時間複雜度為 O(m*n) ，空間複雜度為 O(m*n) 。

解答

class Solution(object):
    def countUnguarded(self, m, n, guards, walls):
        """
        :type m: int
        :type n: int
        :type guards: List[List[int]]
        :type walls: List[List[int]]
        :rtype: int
        """
        grid = [[0]*n for _ in range(m)]
        for i,j in guards:
            grid[i][j] = 2
        for i,j in walls:
            grid[i][j] = 2
        for i,j in guards:
            for dx,dy in [[-1,0],[1,0],[0,-1],[0,1]]:
                x = i+dx
                y = j+dy
                while 0<=x<m and 0<=y<n and (grid[x][y]==0 or grid[x][y]==1):
                    grid[x][y] = 1
                    x += dx
                    y += dy
        return sum(grid[i][j]==0 for i in range(m) for j in range(n))

執行結果

47 / 47 test cases passed.
Status: Accepted
Runtime: 2600 ms
Memory Usage: 45.1 MB

原題連結

http://leetcode.com/contest/biweekly-contest-77/problems/count-unguarded-cells-in-the-grid/

您的支援是我最大的動力

「」
「」