面试编程题解题思路（二）

0x01 深度优先搜索

题目描述：

这种题解题思路在于将连接在一起的‘1’看作是一个整体，可以将二维数组看成是无向图，每个‘1’之间都连接着一条线

从头到尾对数组进行遍历，碰到‘1’就进行深度搜索，将搜索到的‘1’全部变为‘0’， 这样发起深度搜索的次数就是岛屿的数量

代码如下：

class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        def dfs(grid, i, j):
            grid[i][j] == 0

            for x, y in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
                if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and grid[x][y] == '1':
                    grid[x][y] =0
                    dfs(grid, x, y)

        
        n_r = len(grid)
        if n_r == 0:
            return 0
        n_l = len(grid[0])

        island_num = 0
        for i in range(n_r):
            for j in range(n_l):
                if grid[i][j] == '1':
                    island_num += 1
                    dfs(grid, i, j)

        return island_num