Python depth first search with an outer loop


  • 0
    M
    class Solution(object):
        def numIslands(self, grid):
            """
            :type grid: List[List[str]]
            :rtype: int
            """
            if not grid:
                return 0
            num_row = len(grid)
            num_col = len(grid[0])
            explored = [[False]*num_col for j in range(num_row)]
            def dfs(x, y):
                if not explored[x][y] and grid[x][y] == '1':
                    explored[x][y] = True
                    if x < num_row-1: #how to simplify the check?
                        dfs(x+1,y)
                    if y < num_col-1:
                        dfs(x,y+1)
                    if x > 0:
                        dfs(x-1,y)
                    if y > 0:
                        dfs(x,y-1)
            c = 0
            for i in range(num_row):
                for j in range(num_col):
                    if grid[i][j] == '1' and not explored[i][j]:
                        dfs(i,j)
                        c += 1
            return c
    

    Any suggestions to check the boundary of the grid?


  • 1
    T

    Hi, you can make the following chage to your dfs(x, y) function:

    def dfs(x, y):
            if x == num_row or y == num_col or x < 0 or y < 0: 
                return
            if not explored[x][y] and grid[x][y] == '1':
                explored[x][y] = True
                map(dfs, (x+1, x, x-1, x), (y, y+1, y, y-1))

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.