from collections import defaultdict
import heapq


def dijkstra(graph, start):
    distances = {node: float("inf") for node in graph}
    distances[start] = 0
    previous_nodes = {node: None for node in graph}
    priority_queue = [(0, start)]
    
    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)
        if current_distance > distances[current_node]:
            continue
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                previous_nodes[neighbor] = current_node
                heapq.heappush(priority_queue, (distance, neighbor))
    return distances, previous_nodes
 

def minimumMoves(grid, startX, startY, goalX, goalY):
    # Write your code here
    nodes = defaultdict(dict)
    length = len(grid[0])
    # create graph of nodes and edges
    for y, row in enumerate(grid):
        for x, column in enumerate(row):
            if grid[y][x] == "X":
                continue
            # move up and add edges
            i, j = x-1, y
            # go left
            while i >= 0 and grid[j][i] != "X":
                nodes[(x, y)][(i, j)] = 1
                i -= 1
            # go right
            i, j = x+1, y
            while i < length and grid[j][i] != "X":
                nodes[(x, y)][(i, j)] = 1
                i += 1
            i, j = x, y-1
            # go down
            while j >= 0 and grid[j][i] != "X":
                nodes[(x, y)][(i, j)] = 1
                j -= 1
            # go up
            i, j = x, y+1
            while j < length and grid[j][i] != "X":
                nodes[(x, y)][(i, j)] = 1
                j += 1
    maps = dijkstra(nodes, (startY, startX))
    return maps[0][(goalY, goalX)]