Problem statement

https://leetcode.com/problems/the-maze-iii/

Solution

What we actually need to find is the shortest distance between two nodes in graph, where distance between two nodes is pair of two values: distance and path, which is string (we need to have pair to break ties when distance is the same). Classical ways to find shortest path include bfs, dfs and Dijkstra algorithm. The following code is for Dijkstra algorithm.

So, we keep heap with 4 values: (distance, path, x coordinate, y coordinate). Then we start to traverse graph, extracting the node with the smallest distance, we simulate ball movement from this node. Note, that there are at least two different ways to perform Dijkstra:

  1. Keep array of visited nodes: when we visit node, we do not need to visit it again.
  2. Keep array of distances (see problem 0787), where we push into heap only if we found shorter distance.

Complexity

Time complexity of this solution is O(mn * max(m,n) * log(mn)), because it is usual Dijkstra complexity, but we potentially can spend (O(max(m,n)) time to go from one node to another. It can be improved to O(mn * log(mn)), if we precalculate all edges.

Code

class Solution:
    def findShortestWay(self, maze, ball, hole):
        if not maze: return False
        m, n = len(maze), len(maze[0])
        dirs = ((1, 0, 'd'),(0, -1, 'l'), (0, 1, 'r'), (-1, 0, 'u'))

        visited = [[0] * n for _ in range(m)]
        pq = [(0, "", ball[0], ball[1])]

        while pq:
            dist, path, x, y = heappop(pq)
            if [x, y] == hole:
                return path

            visited[x][y] = True

            for dx, dy, symb in dirs:
                new_dist, new_x, new_y = dist, x, y

                while m > new_x+dx >= 0 and n > new_y+dy >= 0 and maze[new_x+dx][new_y+dy] != 1:
                    new_x += dx
                    new_y += dy
                    new_dist += 1
                    if [new_x, new_y] == hole:
                        break
                    
                if not visited[new_x][new_y]:
                    heappush(pq, (new_dist, path + symb, new_x, new_y) )
                
        return "impossible"