private static readonly List<(int dx, int dy)> directions = new()
    {
        (1, 0), (-1, 0), (0, 1), (0, -1)
    };

    public static int minimumMoves(List<string> grid, int startX, int startY, int goalX, int goalY)
    {
        var len = grid.Count;
        var queue = new Queue<(int cx, int cy, int moves)>();
        var visited = new bool[len, len];
        
        queue.Enqueue((startX, startY, 0));
        visited[startX, startY] = true;
        
        while(queue.Count > 0)
        {
            var (cx, cy, moves) = queue.Dequeue();
            
            if(cx == goalX && cy == goalY)
            {
                return moves;
            }
            
            foreach(var (dx, dy) in directions)
            {
                var (nx, ny) = (cx + dx, cy + dy);
                while (nx >= 0 && nx < len && 
                    ny >= 0 && ny < len && 
                    grid[nx][ny] == '.')
                {
                    if (!visited[nx, ny])
                    {
                        visited[nx, ny] = true;
                        queue.Enqueue((nx, ny, moves + 1));
                    }

                    nx += dx;
                    ny += dy;
                }
            }
        }
        
        return -1;
    }

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