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)]

from collections import deque

def minimumMoves(grid, startX, startY, goalX, goalY):
    # Initialize steps matrix with -1 for empty cells, -2 for obstacles
    steps = [[-1 if cell == '.' else -2 for cell in row] for row in grid]
    steps[startX][startY] = 0  # Start position has 0 steps
    
    # Initialize queue for BFS traversal
    dq = deque([(startX, startY)])
    
    # Define directions: UP, DOWN, LEFT, RIGHT
    directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]
    
    # Grid dimensions
    row, col = len(grid), len(grid[0])
    
    # Perform BFS
    while dq:
        x, y = dq.popleft()
        next_step = steps[x][y] + 1
        
        # Explore 4 directions
        for dx, dy in directions:
            i, j = x + dx, y + dy
            
            # Check boundary and obstacle conditions
            while 0 <= i < row and 0 <= j < col and steps[i][j] != -2:
                if steps[i][j] == -1:  # If unvisited, mark with next step
                    steps[i][j] = next_step
                    dq.append((i, j))
                else:  # If visited, update steps if new path is shorter
                    steps[i][j] = min(steps[i][j], next_step)
                i, j = i + dx, j + dy

    return steps[goalX][goalY]  # Return steps to goal position

public static int minimumMoves(List<string> grid, int startX, int startY, int goalX, int goalY)
    {
        List<StringBuilder> gridBuilder = new List<StringBuilder>();
        for (int i = 0; i < grid.Count; i++)
        {
            gridBuilder.Add(new StringBuilder(grid[i]));
        }
        Queue<int[]> queue = new Queue<int[]>();
        int n = grid.Count;
        
        // table to keep track
        var track = new int[n,n];
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
                track[i,j] = 0;

        queue.Enqueue([startX, startY]);
                
        while(queue.Count > 0){
            var arr = queue.Dequeue();
            int currentX = arr[0];
            int currentY = arr[1];

            if(currentX >= n|| currentX < 0 ||
                currentY >=  n || currentY < 0 ||
                gridBuilder[currentX][currentY] == 'X' ||
                gridBuilder[currentX][currentY] == '0')
                    continue;


            // Mark as visited
            gridBuilder[currentX][currentY] = '0';

            if (currentX == goalX && currentY == goalY){
                break;
            }

            int count = track[currentX, currentY] + 1;
            // Down
            int index = currentX + 1;
            while(index < n && gridBuilder[index][currentY] != 'X'  && gridBuilder[index][currentY] != '0'){
                 if(track[index, currentY] == 0){
                    queue.Enqueue([index, currentY]);
                    track[index, currentY] = count;
                 }
                index++;
            }
            // Up
            index = currentX - 1;
            while(index >= 0 && gridBuilder[index][currentY] != 'X'  && gridBuilder[index][currentY] != '0'){
                if(track[index, currentY] == 0){
                    queue.Enqueue([index, currentY]);
                    track[index, currentY] = count;
                }
                index--;
            }
            // Right
            index = currentY + 1;
            while(index < n && gridBuilder[currentX][index] != 'X'  && gridBuilder[currentX][index] != '0'){
                if(track[currentX, index] == 0){
                    queue.Enqueue([currentX, index]);
                    track[currentX, index] = count;
                }
                index++;
            }

            // Left
            index = currentY - 1;
            while(index >= 0 && gridBuilder[currentX][index] != 'X'  && gridBuilder[currentX][index] != '0'){
                if(track[currentX, index] == 0){
                    queue.Enqueue([currentX, index]);
                    track[currentX, index] = count;
                }
                index--;
            }
        }
        return track[goalX, goalY];
    }