# Python Code

• class Solution(object):

``````def findShortestWay(self, maze, ball, hole):

"""

:type maze: List[List[int]]

:type ball: List[int]

:type hole: List[int]

:rtype: str

"""

def up(s):

dist = 0
c = s

while c[0] >0 and maze[c[0]-1][c[1]] !=1:
dist += 1
c = (c[0]-1,c[1])

return c, dist

def down(s):

dist = 0
c = s

while c[0] <len(maze)-1 and maze[c[0]+1][c[1]] !=1:
dist += 1
c = (c[0]+1,c[1])

return c, dist

def left(s):

dist = 0
c = s

while c[1] >0 and maze[c[0]][c[1]-1] !=1:
dist += 1
c = (c[0],c[1]-1)

return c, dist

def right(s):

dist = 0
c = s

while c[1] <len(maze[0])-1 and maze[c[0]][c[1]+1] !=1:
dist += 1
c = (c[0],c[1]+1)

return c, dist

def IsPassHole(cpos,npos):

xmove,ymove = npos[0] - cpos[0], npos[1] - cpos[1]

xsep, ysep = hole[0] - cpos[0], hole[1] - cpos[1]

if xsep == 0:
if ysep*ymove>-1 and abs(ymove) - abs(ysep) >-1:
return True, abs(ysep)

if ysep == 0:
if xsep*xmove>-1 and abs(xmove) - abs(xsep) >-1:
return True, abs(xsep)

return False, 0

def Direction(c,n):
if n[0] > c[0]:
return 'd'
if n[1] > c[1]:
return 'r'
if c[0] > n[0]:
return 'u'
if c[1] > n[1]:
return 'l'

record = {(ball[0],ball[1]):{'dist':0,'pre':""}}

stack = [{"pos":(ball[0],ball[1]),"dist":0,"pre":""}]

traces = {}

while len(stack)>0:

current = stack.pop(0)

#print current
dist = current['dist']
pos = current['pos']
pre = current["pre"]

n_up,d_up = up(pos)
n_down,d_down = down(pos)
n_left,d_left = left(pos)
n_right,d_right = right(pos)

#d_up, d_down, d_left, d_right = [one +dist for one in (d_up,d_down,d_left, d_right)]

for n_pos,n_dist in [(n_down,d_down),(n_left,d_left),(n_right,d_right),(n_up,d_up)]:

if n_dist<1:
continue

judge ,sep = IsPassHole(pos, n_pos)

n_dist += dist

if judge:
rpos = pre+ Direction(pos, n_pos)
#print pos,n_pos, rpos
if sep+dist in traces:
traces[sep+dist] += [rpos]
else:
traces[sep+dist] = [rpos]
continue

if (n_pos not in record):

di = Direction(pos, n_pos)
record[n_pos] = {'dist':n_dist, 'pre':pre+di}
stack += [{"pos": n_pos, "dist":n_dist,"pre":pre+di}]
continue

if (n_dist < record[n_pos]["dist"]):

di = Direction(pos, n_pos)
npre = pre+di
record[n_pos] = {'dist':n_dist, 'pre':npre}
stack += [{"pos": n_pos, "dist":n_dist,"pre":npre}]

if (n_dist == record[n_pos]["dist"]):

di = Direction(pos, n_pos)
npre = min(pre+di,record[n_pos]["pre"])
record[n_pos] = {'dist':n_dist, 'pre':npre}
stack += [{"pos": n_pos, "dist":n_dist,"pre":npre}]

if len(traces)<1:
return "impossible"

#print record
#print record[4,5]

#print sorted(traces.items())
return min(sorted(traces.items())[0][1])``````

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