Python Beat 86% Simple DFS Solution


  • 1
    D
    class Solution(object):
        def hasPath(self, maze, start, destination):
            """
            :type maze: List[List[int]]
            :type start: List[int]
            :type destination: List[int]
            :rtype: bool
            """
            visited = set()
            m, n = len(maze), len(maze[0])
            reachable = [False]
            def dfs(curr):
                i, j = curr
                if curr in visited: return
                if tuple(destination) == curr: 
                    reachable[0] = True
                    return
                visited.add(curr)
                
                right_j = left_j = j
                while right_j < n and maze[i][right_j]==0: right_j += 1 # ->
                while left_j >=0 and maze[i][left_j]==0: left_j -= 1 # <-
                
                up_i = down_i = i
                while up_i >= 0 and maze[up_i][j]==0:up_i-=1 # up
                while down_i<m and maze[down_i][j]==0:down_i+=1 # down
                
                dfs((i, right_j-1))
                dfs((i, left_j+1))
                dfs((up_i+1, j))
                dfs((down_i-1, j))
            
            dfs(tuple(start))
            return reachable[0] 
                
                
                
    

Log in to reply
 

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