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();
    }
}