LeetCode 200. Number of Islands

Posted on | In |
Words count in article: 213 | Reading time ≈ 1

题目

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

思路

DFS.
遍历时对每个“1”进行dfs，把它及相连的位置全部变成“0”，这样就能把一个点推广到一个岛，从而得到岛的数目。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        res = 0
        for r in range(len(grid)):
            for c in range(len(grid[0])):
                if grid[r][c] == '1':
                    self.dfs(grid, r, c)
                    res += 1
        return res
    
    def dfs(self, grid, i, j):
        dirs = [[0, -1], [0, 1], [-1, 0], [1, 0]]
        grid[i][j] = '0'
        for d in dirs:
            nr, nc = i+d[0], j+d[1]
            if nr >= 0 and nc >= 0 and nr < len(grid) and nc < len(grid[0]):
                if grid[nr][nc] == '1':
                    self.dfs(grid, nr, nc)