LeetCode:200. Number of Islands

发表于 | 分类于

题目描述

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:

1
2
3
4
5
6
7
Input:
11110
11010
11000
00000

Output: 1

Example 2:

1
2
3
4
5
6
7
Input:
11000
11000
00100
00011

Output: 3

这题需要一个额外的二维数组，来记录某一个点是否被检查过。然后我们需要对所有的点按顺序进行一次深度优先搜索，如果说这个点已经被检查过，则不再搜索。那么，一开始需要进行搜索的点的个数，就是岛屿的数量。

代码实现

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
class Solution:
    def __init__(self):
        self.count = 0
        self.matrix = None

    def numIslands(self, grid: 'list[list[str]]') -> 'int':
        if len(grid) == 0:
            return 0
        if len(grid[0]) == 0:
            return 0

        self.matrix = [[0] * len(grid[0]) for _ in range(len(grid))]

        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1' and self.matrix[i][j] == 0:
                    self.count += 1
                    self.dfs(i, j, grid)

        return self.count

    def dfs(self, x, y, grid):
        if grid[x][y] == '1':
            self.matrix[x][y] = 1
            if x > 0 and self.matrix[x-1][y] == 0:
                self.dfs(x-1, y, grid)
            if y > 0 and self.matrix[x][y-1] == 0:
                self.dfs(x, y-1, grid)
            if x < len(grid)-1 and self.matrix[x+1][y] == 0:
                self.dfs(x+1, y, grid)
            if y < len(grid[0])-1 and self.matrix[x][y+1] == 0:
                self.dfs(x, y+1, grid)