GoCalf Calf 的自留地 · 昙花一现

200. Number of Islands

Calf

Problem

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

https://leetcode.com/problems/number-of-islands/

Example 1:

Input:

c++ 
grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]

Output: 1

Example 2:

Input:

c++ 
grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]

Output: 3

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • grid[i][j] is '0' or '1'.

Test Cases

python 
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
solution_test.py下载完整源码
py 
import pytest

from solution import Solution


@pytest.mark.parametrize('grid, expected', [
    ([
        ["1", "1", "1", "1", "0"],
        ["1", "1", "0", "1", "0"],
        ["1", "1", "0", "0", "0"],
        ["0", "0", "0", "0", "0"],
    ], 1),
    ([
        ["1", "1", "0", "0", "0"],
        ["1", "1", "0", "0", "0"],
        ["0", "0", "1", "0", "0"],
        ["0", "0", "0", "1", "1"],
    ], 3),

    ([["1","1","1"],["0","1","0"],["0","1","0"]], 1),
])
class Test:
    def test_solution(self, grid, expected):
        sol = Solution()
        assert sol.numIslands(grid) == expected

Thoughts

计算机图形学中的漫填充算法。

如果当前位置是陆地，把它改成水，然后看上下左右四个位置，如果有陆地就放到栈里。每次对出栈的位置做相同的处理。这样把整个岛屿都改成水了。

扫描整个区域，每发现一块陆地就用漫填充算法把相连的陆地都换成水，记录次数。

Code

solution.py下载完整源码
py 
class Solution:
    def numIslands(self, grid: list[list[str]]) -> int:
        m = len(grid)
        n = len(grid[0])
        cnt = 0

        for i, row in enumerate(grid):
            for j, v in enumerate(row):
                if v == '0':
                    continue

                cnt += 1
                grid[i][j] = '0'
                stack = [(i, j)]
                while stack:
                    r, c = stack.pop()
                    if r > 0 and grid[r-1][c] == '1':
                        grid[r-1][c] = '0'
                        stack.append((r-1, c))
                    if r < m-1 and grid[r+1][c] == '1':
                        grid[r+1][c] = '0'
                        stack.append((r+1, c))
                    if c > 0 and grid[r][c-1] == '1':
                        grid[r][c-1] = '0'
                        stack.append((r, c-1))
                    if c < n-1 and grid[r][c+1] == '1':
                        grid[r][c+1] = '0'
                        stack.append((r, c+1))

        return cnt

评论需要 JavaScript。