【题目描述】

【思路解析】

二维深度优先搜索问题，需要用一个visited数组来表示每一个节点是否被访问过。检测所有节点，但是只有遇到值为1，并且没有被访问过的节点时才开始以该节点为起点进行深度优先搜索。这个问题之所以简单，是因为他只是深度优先搜索，但是并没有回溯的过程，访问到最后一个节点就结束，并未向上一层递归返回变量或者数值。

时间复杂度和空间复杂度都是O(length*width).

【源代码】

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        length = len(grid)
        if length == 0:
            return 0
        width = len(grid[0])
        self.directions = [[-1, 0], [0, -1], [1, 0], [0, 1]]
        marked = [[0 for _ in range(width)] for _ in range(length)]
        re = 0
        for i in range(length):
            for j in range(width):
                if  marked[i][j]==0 and grid[i][j] == '1':
                    re += 1
                    self.dfs(grid, i, j, length, width, marked)
        return re

    def dfs(self, grid, i, j, length, width, marked):
        marked[i][j] = 1
        for x in range(4):
            x0= i + self.directions[x][0]
            y0= j + self.directions[x][1]
            if 0<=x0<length and 0<=y0<width and marked[x0][y0]==0 and grid[x0][y0]=='1':
                self.dfs(grid, x0, y0, length, width, marked)
复制代码