Python simple Memoization DFS with comments


  • 0
    class Solution(object):
        def findShortestWay(self, maze, ball, hole):
            """
            :type maze: List[List[int]]
            :type ball: List[int]
            :type hole: List[int]
            :rtype: str
            """
            self.memo = {}
            move = collections.defaultdict(dict)
            self.PATH, self.acc = "impossible", float('inf')
            m, n = len(maze), len(maze[0]) if maze else 0
            # build moving graph for each node
            for i, row in enumerate(maze):
                for j, wall in enumerate(row):
                    if wall: continue
                    up = down = i
                    while up > 0 and not maze[up-1][j]: up -= 1
                    while down < m-1 and not maze[down+1][j]: down += 1
                    left = right = j
                    while left > 0 and not maze[i][left-1]: left -= 1
                    while right < n-1 and not maze[i][right+1]: right += 1
                    if up != i: move[(i, j)]["u"] = ((up, j), i-up)
                    if down != i: move[(i, j)]["d"] = ((down, j), down-i)
                    if left != j: move[(i, j)]["l"] = ((i, left), j-left)
                    if right != j: move[(i, j)]["r"] = ((i, right), right-j)
                    
            def dfs((i, j), path, Dist):
                # quit current dfs if accumulative distance is bigger than previous 
                if (i, j) in self.memo and self.memo[(i, j)] < Dist: return
                # update memo
                self.memo[(i, j)] = Dist
                for m in move[(i, j)]:
                    (I, J), dist = move[(i, j)][m]
                    # if ball can reach the hole after this move "m"
                    if (I==i==hole[0] and (J-hole[1])*(j-hole[1]) <= 0) \
                    or (J==j==hole[1] and (I-hole[0])*(i-hole[0]) <= 0):
                        last_dist = abs(j-hole[1]) or abs(i-hole[0])
                        #update answer
                        if (Dist + last_dist, path + m) < (self.acc, self.PATH):
                            self.acc, self.PATH = Dist + last_dist, path + m
                        return
                    dfs((I, J), path + m, Dist+dist)
                    
            dfs(tuple(ball), "", 0)
            return self.PATH
    

Log in to reply
 

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