python solution using DFS w/ path


  • 0
    F
    def dfs(g, start, goal):
        stack = [[start,set([tuple(start)]),0,'']]
        m,n = len(g), len(g[0])
        length = float('inf')
        s='z'
        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)
                continue
            
            # 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
                step=0
                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):
                        break
                
                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
    F

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


  • 0
    F

    @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.