leetcode 2257. Count Unguarded Cells in the Grid(python)
描述
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/
您的支援是我最大的動力
- linux 安裝 ES 8.0 和 kibana 8.0 爬米共坑
- ES 8.0 及其生態配置過程一條龍服務
- 2022 年中紀
- leetcode 1048. Longest String Chain(python)
- leetcode 1354. Construct Target Array With Multiple Sums(python)
- leetcode 2311. Longest Binary Subsequence Less Than or Equal to K(python)
- leetcode 2304. Minimum Path Cost in a Grid(python)
- leetcode 2303. Calculate Amount Paid in Taxes(python)
- 帶你輕鬆入門 Bert
- leetcode 1332. Remove Palindromic Subsequences(python)
- leetcode 3. Longest Substring Without Repeating Characters (python)
- leetcode 2296. Design a Text Editor (python)
- leetcode 2293. Min Max Game(python)
- leetcode 1584. Min Cost to Connect All Points(python)
- leetcode 318. Maximum Product of Word Lengths(python)
- 沙灘 美女才是夏天的正確開啟方式
- leetcode 2275. Largest Combination With Bitwise AND Greater Than Zero (python)
- leetcode 2258. Escape the Spreading Fire(python)
- leetcode 2257. Count Unguarded Cells in the Grid(python)
- leetcode 2273. Find Resultant Array After Removing Anagrams(python)