Python DFS

  • 0
    def hasPath(self, maze, start, destination):
        m, n = len(maze), len(maze[0])
        directions = [(1,0), (-1,0), (0, 1), (0, -1)]
        visited = set()
        def dfs(x, y):
            if x == destination[1] and y == destination[0]:
                return True
            if (x, y) in visited:
                return False
            for d in directions:
                xx, yy = x, y
                while 0<=xx<n and 0<=yy<m and (not maze[yy][xx]):
                    xx += d[0]
                    yy += d[1]
                xx -= d[0]
                yy -= d[1]
                if dfs(xx, yy):
                    return True
            return False
        return dfs(start[1], start[0])

Log in to reply

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