Python Code [456ms]


  • 0
    L

    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

Log in to reply
 

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