# python solution using DFS w/ path

• ``````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)
``````

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

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

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