One algorithm of the day — Leetcode 200– Number of islands — Python

【 topic description 】

【 答 案 】

Two-dimensional depth-first search problem requires a Visited array to indicate whether each node has been visited. All nodes are detected, but only a depth-first search starts at a node with a value of 1 that has not been visited. This problem is simple because it is a depth-first search, but there is no backtracking process, stopping at the last node and not returning variables or values recursively up one level.

Time complexity and space complexity are O(length*width).

【 Source code 】

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)
Copy the code