欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode 1020. Number of Enclaves 解题报告(python)

程序员文章站 2022-07-15 12:43:15
...

1020. Number of Enclaves

  1. 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.

LeetCode 1020. Number of Enclaves 解题报告(python)

解析

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