[LeetCode]200 岛屿的个数

题目描述

给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。

一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例1

输入:
    11110
    11010
    11000
    00000
输出: 1

示例2

输入:
    11000
    11000
    00100
    00011
输出: 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
class Solution:
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        if len(grid)==0:
            return 0
        def dfs(x,y,grid,height,width):
            grid[x][y]=-1
            if x>0 and grid[x-1][y]=='1':
                dfs(x-1,y,grid,height,width)
            if x<(height-1) and grid[x+1][y]=='1':
                dfs(x+1,y,grid,height,width)
            if y>0 and grid[x][y-1]=='1':
                dfs(x,y-1,grid,height,width)
            if y<(width-1) and grid[x][y+1]=='1':
                dfs(x,y+1,grid,height,width)
        
        height=len(grid)
        width=len(grid[0])
        num=0
        for x in range(height):
            for y in range(width):
                if grid[x][y]=='1':
                    dfs(x,y,grid,height,width)
                    num=num+1
        return num