Problem statement

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

Solution

Very similar to Problem 0499 Maze III, this problem is simpler version of it, here is solution, using Dijkstra algorithm.

Complexity

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 shortestDistance(self, maze, start, destination):
        if not maze: return False
        m, n = len(maze), len(maze[0])
        dirs = ((1, 0), (0, -1), (0, 1), (-1, 0))
        
        visited = [[0] * n for _ in range(m)]
        heap = []
        heappush(heap, (0, start[0], start[1]))
        
        while heap:
            pt = heappop(heap)
            if pt[1:3] == tuple(destination):
                return pt[0]

            visited[pt[1]][pt[2]] = True

            for dx, dy in dirs:
                distance, newRow, newCol = pt

                while m>newRow+dx>=0 and n>newCol+dy>=0 and maze[newRow+dx][newCol+dy] != 1:
                    newRow += dx
                    newCol += dy
                    distance += 1
                    
                if not visited[newRow][newCol]:
                    heappush(heap, (distance, newRow, newCol) )
                
        return -1