200. Number of Islands

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:

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:

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

1 2	class Solution: def numIslands(self, grid: List[List[str]]) -> int:

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

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

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。