import heapq
class Solution:
    def shortestDistance(self, maze, start, destination):
        if len(maze) == 0 or len(maze[0]) == 0: return False
        n, m = len(maze), len(maze[0])
        directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]
        visited = [[0 for i in range(m)] for j in range(n)]
        distance = [[float("inf") for i in range(m)] for j in range(n)]
        visited[start[0]][start[1]] = 1
        distance[start[0]][start[1]] = 0
        q = [(0, start[0], start[1])]
        while q:
            dist, i, j = heapq.heappop(q)
            if i == destination[0] and j == destination[1]:
                return distance[i][j]
            for ii, jj in directions:
                temp_i, temp_j = i, j
                step = 0
                while 0<=temp_i+ii<n and 0<=temp_j+jj<m:
                    if maze[temp_i+ii][temp_j+jj] == 0:
                        step += 1
                        temp_i += ii
                        temp_j += jj
                    else:
                        break
                if visited[temp_i][temp_j] == 0 or distance[temp_i][temp_j] > distance[i][j] + step:
                    visited[temp_i][temp_j] = 1
                    distance[temp_i][temp_j] = min(distance[temp_i][temp_j], distance[i][j] + step)
                    heapq.heappush(q, (distance[temp_i][temp_j], temp_i, temp_j))
        return -1