LeetCode-200. Number of Islands

0.原题

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:

Input:
11110
11010
11000
00000

Output: 1

Example 2:

Input:
11000
11000
00100
00011

Output: 3

 

1.代码

class Solution:
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        self.row_num = len(grid)
        if self.row_num == 0:
            return 0
        self.column_num = len(grid[0])
        self.visited = [[False for _ in range(self.column_num)] for _ in range(self.row_num)]
        islands = []
        for r in range(self.row_num):
            for c in range(self.column_num):
                if not self.visited[r][c] and grid[r][c] == '1':
                    island = []
                    self.visit(grid,r,c,island)
                    islands.append(island)
        return len(islands)

    def visit(self,grid,row,column,island):
        if not self.visited[row][column] and  grid[row][column] == '1':
            self.visited[row][column] = True
            island.append((row,column))
            if row - 1 >= 0:
                self.visit(grid,row-1,column,island)
            if row + 1 < self.row_num:
                self.visit(grid,row+1,column,island)
            if column - 1 >= 0:
                self.visit(grid,row,column-1,island)
            if column + 1 < self.column_num:
                self.visit(grid,row,column+1,island)

 

2.思路

首先，我们先解析题意：

给定一个数组，‘1’表示陆地，‘0’表示水域，陆地可以通过水平或者垂直方向连接成一个整体；当一块陆地被水域所包围，那么就形成了一座岛屿；要求根据数组，推算出岛屿的数量。

比如：

数组中，所有的“1”连接成了一个岛屿，那么岛屿数量为:1

 

接下来，我们思考一下，如何判定“相接区域”：

我们知道，如果两块区域数值都为“1”，则这两块区域都是“陆地”；

假如选定一个位置（x,y）,那么通过判断（x,y）的(x-1,y),(x+1,y),(x,y-1),(x,y+1)四个位置的数值是否也为“1”，即可知道(x,y)位置是否与其他“陆地”相接；

如果这两块区域相接，那么就可合并为一块，在程序的表现即为，判断值是否相等，相等即将两块区域添加到同一个列表中。

之后，通过递归的方式，再分别查找(x-1,y),(x+1,y),(x,y-1),(x,y+1)四个位置的“相接陆地”。

当所有相接的“陆地”都被查找完成后，递归结束。