leetcode/DepthFirstSearch/200_NumberOfIslands.py at master · cls1991/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
# coding: utf8


"""
    题目链接: https://leetcode.com/problems/number-of-islands/description.
    题目描述:

    Given a 2d grid map of '1's (land) and '0's (water), count 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.

    Example 1:

        11110
        11010
        11000
        00000
        Answer: 1

    Example 2:

        11000
        11000
        00100
        00011
        Answer: 3

    Credits:
    Special thanks to @mithmatt for adding this problem and creating all test cases.

"""


class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        if not grid or not grid[0]:
            return 0

        islands = 0
        rows, columns = len(grid), len(grid[0])
        for i in range(rows):
            for j in range(columns):
                if self.dfs(grid, rows, columns, i, j):
                    islands += 1

        return islands

    def dfs(self, grid, rows, columns, i, j):
        if i < 0 or i >= rows or j < 0 or j >= columns or grid[i][j] == '0':
            return 0

        grid[i][j] = '0'
        self.dfs(grid, rows, columns, i - 1, j)
        self.dfs(grid, rows, columns, i, j + 1)
        self.dfs(grid, rows, columns, i + 1, j)
        self.dfs(grid, rows, columns, i, j - 1)

        return 1