LeetCode 1020. Number of Enclaves 解题报告(python)
程序员文章站
2022-07-15 12:43:15
...
1020. Number of Enclaves
- Number of Enclaves python solution
题目描述
Given a 2D array A, each cell is 0 (representing sea) or 1 (representing land)
A move consists of walking from one land square 4-directionally to another land square, or off the boundary of the grid.
Return the number of land squares in the grid for which we cannot walk off the boundary of the grid in any number of moves.
解析
1代表小岛,0代表海洋。题目要求我们从边界出发,遍历所有小岛,求得不能到达小岛的个数。
class Solution:
def numEnclaves(self, A: List[List[int]]) -> int:
m, n = len(A), len(A[0])
def dfs(i, j):
A[i][j] = 0
for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1):
if 0 <= x < m and 0 <= y < n and A[x][y]:
dfs(x, y)
for i in range(m):
for j in range(n):
if A[i][j] == 1 and (i == 0 or j == 0 or i == m - 1 or j == n - 1):
dfs(i, j)
return sum(sum(row) for row in A)
Reference
https://leetcode.com/problems/number-of-enclaves/discuss/265534/Python-clean-DFS-solution
上一篇: 【java】BigDecimal使用注意
下一篇: 报表自动化: 抓住时间流逝的瞬间
推荐阅读
-
[leetcode] 306. Additive Number 解题报告
-
LeetCode 1020. Number of Enclaves 解题报告(python)
-
LeetCode 1254. Number of Closed Islands解题报告(python)
-
【LeetCode】450. 删除二叉搜索树中的节点 解题报告 (python)
-
LeetCode 1249. Minimum Remove to Make Valid Parentheses解题报告(python)
-
[leetcode] 306. Additive Number 解题报告
-
【LeetCode】430. Flatten a Multilevel Doubly Linked List 解题报告(Python)
-
LeetCode 347. Top K Frequent Elements解题报告(python)
-
LeetCode 1267. Count Servers that Communicate解题报告(python)