python solution using DFS w/ path

  • 0
    def dfs(g, start, goal):
        stack = [[start,set([tuple(start)]),0,'']]
        m,n = len(g), len(g[0])
        length = float('inf')
        rev = {'u':'d','d':'u','l':'r','r':'l','':''}
        while stack:
            node, path, steps, directions = stack.pop()
            #print node, path, steps, directions
            if node == tuple(goal):
                if steps<length:
                    length = steps
                    s = directions
                elif steps==length:
                    s = min(s, directions)
            # stop if current path has already exceeded length
            if steps >= length: continue
            x, y = node
            for i,j,d in [(-1,0,'u'),(1,0,'d'),(0,1,'r'),(0,-1,'l')]:
                # don't explore the same direction or reverse
                if d == directions[-1:] or d == rev[directions[-1:]]:continue
                u,v = x,y
                while 0<=u+i<m and 0<=v+j<n and g[u+i][v+j]==0:
                    u,v = u+i, v+j
                    step +=1
                    # break if we reached hole
                    if (u,v) == tuple(goal):
                if (u,v) not in path and steps+step<=length:
                    stack.append([(u,v), path | set([(u,v)]), steps+step, directions+d])
        return s if s!='z' else 'impossible'
    class Solution(object):
        def findShortestWay(self, maze, ball, hole):
            :type maze: List[List[int]]
            :type ball: List[int]
            :type hole: List[int]
            :rtype: str
            return dfs(maze, ball, hole)

  • 0

    except I don't understand why example 2 should return 'impossible'

  • 0

    @frankz306 i misunderstood the problem. the ball won't stop until hit the wall.

Log in to reply

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