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:

11110
11010
11000
00000

Answer: 1

解题方法

就是正常的DFS解法，遇到一个为1的就dfs它的所有neighbor,用一个visited matrix 来记录visit过的点，也可以选择将visit过的点变成其他字符比如 "#"

矩阵四个方向遍历，用dx,dy两个array的code比较clean

注意点

• dfs
• 四个方向探索
• check是否valid的条件（边界，是否visit过，是否为1）

Solution

class Solution(object):

    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """

        row_num = len(grid)
        if row_num == 0:
            return 0
        col_num = len(grid[0])
        dx = [-1, 1, 0, 0]
        dy = [0, 0, -1, 1]
        visited = [[False for j in range(col_num)] for i in range(row_num)]
        count = 0

        def dfs(i, j):
            visited[i][j] = True
            for k in range(4):
                nx = i + dx[k]
                ny = j + dy[k]
                if nx >= 0 and nx < row_num and ny >= 0 and ny < col_num and not visited[nx][ny] and grid[nx][ny]:
                    dfs(nx, ny)


        for i in range(row_num):
            for j in range(col_num):
                if not visited[i][j] and grid[i][j]:
                    dfs(i, j)
                    count += 1

        return count

Reference