# Python Code [456ms]

• class Solution(object):

``````def findShortestWay(self, maze, ball, hole):
"""
:type maze: List[List[int]]
:type ball: List[int]
:type hole: List[int]
:rtype: str
"""
M = len(maze)
N = len(maze[0])
MAXL = 9000
preLenRecord = [[MAXL for i in range(N)] for j in range(M)]
rLength, rPath = self.searchHole(maze,hole,ball[0],ball[1],M,N,MAXL,preLenRecord,0)
if rLength >= MAXL:
return 'impossible'
return rPath

def searchHole(self,maze,hole,i,j,M,N,MAXL,preLenRecord,preLen):
preLenRecord[i][j] = preLen
fLen = MAXL
fPath = ''
if [i,j] == hole:
return 0, ''
#search down
if i < M-1:
if maze[i+1][j] == 0:
down = i + 1
while down < M:
if [down,j] == hole:
return down-i,'d'
if maze[down][j] == 1:
break
down += 1
down -= 1
if preLen + down-i < preLenRecord[down][j]:
r1,r2 = self.searchHole(maze,hole,down,j,M,N,MAXL,preLenRecord,preLen+down-i)
if fLen > r1+down-i:
fLen = r1+down-i
fPath = 'd'+ r2
#search left
if j > 0:
if maze[i][j-1] == 0:
left = j-1
while left > -1:
if [i,left] == hole:
return j-left,'l'
if maze[i][left] == 1:
break
left -= 1
left += 1
if preLen + j-left < preLenRecord[i][left]:
r1,r2 = self.searchHole(maze,hole,i,left,M,N,MAXL,preLenRecord,preLen+j-left)
if fLen > r1+j-left:
fLen = r1+j-left
fPath = 'l'+r2
#search right
if j < N-1:
if maze[i][j+1] == 0:
right = j+1
while right < N:
if [i,right] == hole:
return right-j,'r'
if maze[i][right] == 1:
break
right += 1
right -= 1
if preLen + right - j < preLenRecord[i][right]:
r1,r2 = self.searchHole(maze,hole,i,right,M,N,MAXL,preLenRecord,preLen+right-j)
if fLen > r1 + right-j:
fLen = r1 + right - j
fPath = 'r'+ r2

#search up
if i > 0:
if maze[i-1][j] == 0:
up = i-1
while up > -1:
if [up,j] == hole:
return i-up,'u'
if maze[up][j] == 1:
break
up -= 1
up += 1
if preLen+i-up < preLenRecord[up][j]:
r1, r2 = self.searchHole(maze,hole,up,j,M,N,MAXL,preLenRecord,preLen+i-up)
if fLen > r1 + i - up:
fLen = r1 + i - up
fPath = 'u' + r2
return fLen,fPath``````

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