NumberOfIslands.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2019/10/28 0:10
# @Author  : tc
# @File    : NumberOfIslands.py
"""
题号200 岛屿数量
给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:

输入:
11110
11010
11000
00000

输出: 1
示例 2:

输入:
11000
11000
00100
00011

输出: 3


题目解读：是说“1”连成一片的地方有几处。比如例1，上面的“1”不都是连在一起的吗，这就算1个，例2上面连着的“1”不是有3处么，这个就算3，这个意思。

多种解法：
1.DFS
2.BFS
3.并查集

参考：https://leetcode-cn.com/problems/number-of-islands/solution/dfs-bfs-bing-cha-ji-python-dai-ma-java-dai-ma-by-l/

"""
from typing import List

class Solution:
    # DFS解法
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid: return 0
        row = len(grid)
        col = len(grid[0])
        cnt = 0

        def dfs(i, j):
            grid[i][j] = "0"
            for x, y in [[-1, 0], [1, 0], [0, -1], [0, 1]]:  # 遍历四个方向
                tmp_i = i + x
                tmp_j = j + y
                if 0 <= tmp_i < row and 0 <= tmp_j < col and grid[tmp_i][tmp_j] == "1":
                    dfs(tmp_i, tmp_j)

        for i in range(row):
            for j in range(col):
                if grid[i][j] == "1":
                    dfs(i, j)
                    cnt += 1
        return cnt

if __name__ == '__main__':
    grid = [
        ['1', '1', '0', '0', '0'],
        ['1', '1', '0', '0', '0'],
        ['0', '0', '1', '0', '0'],
        ['0', '0', '0', '1', '1'],
    ]

    solution = Solution()
    print(solution.numIslands(grid))