| 123456789101112131415161718192021222324252627282930313233343536373839404142 |
- from typing import List
- class Solution:
- def closedIsland(self, grid: List[List[int]]) -> int:
- res = 0
- m, n = len(grid), len(grid[0]),
- for i in range(m):
- self.dfs(grid, i, 0)
- self.dfs(grid, i, n - 1)
- for j in range(n):
- self.dfs(grid, 0, j)
- self.dfs(grid, m - 1, j)
- for i in range(m):
- for j in range(n):
- if grid[i][j] == 0:
- res += 1
- self.dfs(grid, i, j)
- return res
- pass
- def dfs(self, grid: List[List[int]], i: int, j: int):
- m, n = len(grid), len(grid[0]),
- if i < 0 or j < 0 or i >= m or j >= n:
- return
- if grid[i][j] == 1:
- return
- grid[i][j] = 1
- self.dfs(grid, i + 1, j)
- self.dfs(grid, i - 1, j)
- self.dfs(grid, i, j + 1)
- self.dfs(grid, i, j - 1)
- pass
- if __name__ == '__main__':
- print(Solution().closedIsland(
- [[1, 1, 1, 1, 1, 1, 1, 0],
- [1, 0, 0, 0, 0, 1, 1, 0],
- [1, 0, 1, 0, 1, 1, 1, 0],
- [1, 0, 0, 0, 0, 1, 0, 1],
- [1, 1, 1, 1, 1, 1, 1, 0]]))
|
