public static int minimumMoves(List<String> grid, int startX, int startY, int goalX, int goalY) {
            int n = grid.size();
            boolean[][] visited = new boolean[n][n];
            Queue<int[]> queue = new LinkedList<>();
            queue.offer(new int[]{startX, startY, 0});
            visited[startX][startY] = true;

            int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

            while (!queue.isEmpty()) {
                int[] current = queue.poll();
                int x = current[0];
                int y = current[1];
                int moves = current[2];

                if (x == goalX && y == goalY) {
                    return moves;
                }

                for (int[] dir : directions) {
                    int newX = x + dir[0];
                    int newY = y + dir[1];

                    while (newX >= 0 && newX < n && newY >= 0 && newY < n && grid.get(newX).charAt(newY) == '.') {
                        if (!visited[newX][newY]) {
                            visited[newX][newY] = true;
                            queue.offer(new int[]{newX, newY, moves + 1});
                        }
                        newX += dir[0];
                        newY += dir[1];
                    }
                }
            }

            return -1; 
        }

def is_valid(grid, i, j):
    return i >=0 and i < len(grid) and j >=0 and j < len(grid[i]) and grid[i][j] != 'X'
    
def span(grid, x, y, graph):
    i, j = x+1, y
    while is_valid(grid, i, j):
        graph[(x, y)].add((i, j))
        i = i+1
    
    i, j = x-1, y
    while is_valid(grid, i, j):
        graph[(x, y)].add((i, j))
        i = i-1
        
    i, j = x, y+1
    while is_valid(grid, i, j):
        graph[(x, y)].add((i, j))
        j = j+1
    
    i, j = x, y-1
    while is_valid(grid, i, j):
        graph[(x, y)].add((i, j))
        j = j-1
    
def build_graph(grid):
    graph = {}
    for i in range(len(grid)):
        for j in range(len(grid[i])):
            if (grid[i][j] != 'X'):
                graph[(i, j)] = set()
                span(grid, i, j, graph)
    return graph

def bfs(start, end, graph):
    q1 = deque()
    q2 = deque()
    
    visited = set()
    
    q1.append(start)
    depth = 0
    
    while len(q1) > 0:
        v = q1.popleft()
        if v == end:
            return depth
        for adj in graph[v]:
            if adj not in visited:
                visited.add(adj)
                q2.append(adj)
        if len(q1) == 0 and len(q2) > 0:
            depth = depth + 1
            q1, q2 = q2, q1
    
    return depth

def minimumMoves(grid, startX, startY, goalX, goalY):
    graph = build_graph(grid)
    start = (startX, startY)
    end = (goalX, goalY)
    return bfs(start, end, graph)

private sealed record PathPoint(int X, int Y, int Direction, int Moves);

public static int MinimumMoves(List<string> grid, int startX, int startY, int goalX, int goalY)
{
    var moveDistances = Enumerable.Range(0, grid.Count).Select(_ => Enumerable.Repeat(int.MaxValue, grid.Count).ToArray()).ToArray();
    var directions = new List<(int Dx, int Dy)> { (-1, 0), (0, -1), (0, 1), (1, 0) };
    var pathQueue = new Queue<PathPoint>();
    var results = new List<int>();

    moveDistances[startX][startY] = 0;
    pathQueue.Enqueue(new PathPoint(startX, startY, -1, 0));

    while (pathQueue.TryDequeue(out var path))
    {
        if (path.X == goalX && path.Y == goalY)
        {
            results.Add(path.Moves);
        }

        for (var i = 0; i < directions.Count; i++)
        {
            var (x, y) = (path.X + directions[i].Dx, path.Y + directions[i].Dy);
            if (x >= 0 && x < grid.Count && y >= 0 && y < grid.Count && grid[x][y] != 'X')
            {
                var moves = path.Moves + (i == path.Direction ? 0 : 1);
                if (moves < moveDistances[x][y])
                {
                    moveDistances[x][y] = moves;
                    pathQueue.Enqueue(new PathPoint(x, y, i, moves));
                }
            }
        }
    }

    return results.Min();
}

function minimumMoves(grid, startX, startY, goalX, goalY) {
    // Write your code here
    const queue = [[startX, startY, 0]];
    const visited = new Set();
    const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];

    while (queue.length > 0) {
        const [x, y, moves] = queue.shift();
        const position = `${x}-${y}`;

        if (x === goalX && y === goalY) {
            return moves;
        }

        visited.add(position);

        for (const [dx, dy] of directions) {
            let newX = x + dx;
            let newY = y + dy;

            while (
                newX >= 0 &&
                newY >= 0 &&
                newX < grid.length &&
                newY < grid.length &&
                grid[newX][newY] !== 'X'
            ) {
                const newPosition = `${newX}-${newY}`;

                if (!visited.has(newPosition)) {
                    queue.push([newX, newY, moves + 1]);
                    visited.add(newPosition);
                }

                newX += dx;
                newY += dy;
            }
        }
    }

    return -1; // If a path is not found
}

class DijkstraNode implements Comparable<DijkstraNode> {
    private final int X;
    private final int Y;
    private int onStep;
    
    public DijkstraNode(int x, int y, int onStep) {
        this.X = x;
        this.Y = y;
        this.onStep = onStep;
    }
        
    public int getOnStep() {
        return onStep;
    }
    
    public void setOnStep(int onStep) {
        this.onStep = onStep;
    }
    
    public int getX() {
        return X;
    }
    
    public int getY() {
        return Y;
    }
    
    @Override
    public int compareTo(DijkstraNode node) {
        return this.X != node.getX() ? (this.X - node.getX()) : (this.Y - node.getY());
    }
    
}

class Result {

    /*
     * Complete the 'minimumMoves' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts following parameters:
     *  1. STRING_ARRAY grid
     *  2. INTEGER startX
     *  3. INTEGER startY
     *  4. INTEGER goalX
     *  5. INTEGER goalY
     */
    
    public static TreeSet<DijkstraNode> findNeighbors(List<String> grid, int x, int y, int onStep, TreeSet<DijkstraNode> alreadyParsed, DijkstraNode goal) {
        
        TreeSet<DijkstraNode> set = new TreeSet<>();
        
        int n = grid.size();
        int m = grid.get(0).length();
        
        for (int i = x + 1; i < n; i++) {
            int j = y;    
            if (grid.get(i).charAt(j) == 'X') {
                break;
            }
            DijkstraNode node = new DijkstraNode(i, j, onStep);
            if (alreadyParsed.contains(node)) {
                break;
            }
            if (node.compareTo(goal) == 0) {
                goal.setOnStep(onStep);
            }
            set.add(node);
        }
        
        for (int i = x - 1; i >= 0; i--) {
            int j = y;
            if (grid.get(i).charAt(j) == 'X') {
                break;
            }
            DijkstraNode node = new DijkstraNode(i, j, onStep);
            if (alreadyParsed.contains(node)) {
                break;
            }
            if (node.compareTo(goal) == 0) {
                goal.setOnStep(onStep);
            }
            set.add(node);
        }
        
        for (int j = y + 1; j < m; j++) {
            int i = x;
            if (grid.get(i).charAt(j) == 'X') {
                break;
            }
            DijkstraNode node = new DijkstraNode(i, j, onStep);
            if (alreadyParsed.contains(node)) {
                break;
            }
            if (node.compareTo(goal) == 0) {
                goal.setOnStep(onStep);
            }
            set.add(node);
        }
        
        for (int j = y - 1; j >= 0; j--) {
            int i = x;
            if (grid.get(i).charAt(j) == 'X') {
                break;
            }
            DijkstraNode node = new DijkstraNode(i, j, onStep);
            if (alreadyParsed.contains(node)) {
                break;
            }
            if (node.compareTo(goal) == 0) {
                goal.setOnStep(onStep);
            }
            set.add(node);
        }
        return set;
    }
    
    public static int minimumMoves(List<String> grid, int startX, int startY, int goalX, int goalY) {

        DijkstraNode node = new DijkstraNode(startX, startY, 0);
        
        DijkstraNode goal = new DijkstraNode(goalX, goalY, 0);
            
        LinkedList<DijkstraNode> queue = new LinkedList<>();
        
        TreeSet<DijkstraNode> alreadyParsed = new TreeSet<>();
                
        queue.add(node);
        alreadyParsed.add(node);
        
        while (!queue.isEmpty()) {
            DijkstraNode primary = queue.pollFirst();
            
            int x = primary.getX();
            int y = primary.getY();
            
            int onStep = primary.getOnStep() + 1;
            
            TreeSet<DijkstraNode> neighbors = findNeighbors(grid, x, y, onStep, alreadyParsed, goal);
            
            if (neighbors.contains(goal)) {
                break;
            }
            
            alreadyParsed.addAll(neighbors);
            queue.addAll(neighbors);
        } 
        return goal.getOnStep();
    }
}