Compact python solution


  • 0
    S
    def findShortestWay(self, maze, ball, hole):
    
        m, n = len(maze), len(maze[0])
        pq = [(0, ball[0], ball[1], "")]
        maze[hole[0]][hole[1]] = 3
        
        while pq:
            dist, i, j, route = heappop(pq)
            if maze[i][j] == -1: continue
            if maze[i][j] == 3: return route
            maze[i][j] = -1
            for di,dj,d in [(0,1,"r"), (0,-1,"l"), (1,0,"d"), (-1,0,"u")]:
                x,y,steps = i,j,0
                while 0<=x+di<m and 0<=y+dj<n and maze[x+di][y+dj]!=1:
                    x += di
                    y += dj
                    steps += 1
                    if maze[x][y] == 3: break
                heappush(pq, (dist+steps, x, y, route+d))
                
        return "impossible"

Log in to reply
 

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