void update(int I, int J, int i, int j, vector<vector<bool>>& visited, vector<vector<int>>& minPath, queue<pair<int, int>>& Q) {
    if (visited[i][j]) return;
    visited[i][j] = true;
    minPath[i][j] = minPath[I][J] + 1;
    Q.push(make_pair(i, j));
    return;
}

int minimumMoves(int n, vector<vector<char>> grid, int startX, int startY, int goalX, int goalY) {
    vector<vector<bool>> visited(n + 2, vector<bool>(n + 2));
    vector<vector<int>> minPath(n + 2, vector<int>(n + 2, -1));
    queue<pair<int, int>> Q;
    Q.push(make_pair(startX, startY));
    visited[startX][startY] = true;
    minPath[startX][startY] = 0;
    while (!Q.empty()) {
        int I = Q.front().first, J = Q.front().second;
        for (int i=1; I - i > 0; i++) {
            if (grid[I-i][J] == 'X') break;
            update(I, J, I-i, J, visited, minPath, Q);
        }
        for (int i=1; I + i < n+1; i++) {
            if (grid[I+i][J] == 'X') break;
            update(I, J, I+i, J, visited, minPath, Q);
        }
        for (int j=1; J - j > 0; j++) {
            if (grid[I][J-j] == 'X') break;
            update(I, J, I, J-j, visited, minPath, Q);
        }
        for (int j=1; J + j < n+1; j++) {
            if (grid[I][J+j] == 'X') break;
            update(I, J, I, J+j, visited, minPath, Q);
        }
        Q.pop();
    }
    return minPath[goalX][goalY];
}

int main()
{
    int n, startX, startY, goalX, goalY;
    string s;
    cin >> n;
    vector<vector<char>> grid(n + 2, vector<char>(n + 2));
    for (int i = 1; i <= n; i++) {
        cin >> s;
        for (int j = 1; j <= n; j++) grid[i][j] = s[j - 1];
    }
    cin >> startX >> startY >> goalX >> goalY;
    cout << minimumMoves(n, grid, startX + 1, startY + 1, goalX + 1, goalY + 1);
}

from dataclasses import dataclass, field
from typing import ClassVar
from functools import cached_property
from itertools import chain

class GameSetup:
    goalX  = 1
    goalY = 2
    grid = ["...", ".X.",'...']


@dataclass(eq=True, order=True)
class Move(GameSetup):
    x: int = field(hash=True, compare=False)
    y: int = field(hash=True, compare=False)
    step:int  = field(default=0, hash=False, compare=True)
    cost:float = field(init=False, hash=False, compare=True)

    def __post_init__(self):
        self.cost = self.get_cost()
    
    def __hash__(self):
        return hash((self.x, self.y))

    @property
    def maxX(self):
        return len(GameSetup.grid)-1
    
    @property
    def maxY(self):
        return len(GameSetup.grid[0])-1

    def get_cost(self) -> float:
        if self.x > self.maxX or self.x < 0 or self.y > self.maxY or self.y < 0:
            scost = 1e9
        elif Move.grid[self.x][self.y] == 'X':
            scost = 1e9
        else:
            scost = (self.goalX-self.x) ** 2 + (self.goalY-self.y) ** 2
        return scost
        
    def all_moves(self):
        row = GameSetup.grid[self.x]
        col = ''.join([r[self.y] for r in GameSetup.grid])
        x_min = max(0, col.rfind('X', 0, self.x))
        xx = col.find('X', self.x)
        if xx == -1:
            xx = self.maxX
        x_max = min(self.maxX, xx)
        print(col, x_min, x_max)
        y_min = max(0, row.rfind('X', 0, self.y))
        yy = row.find('X', self.y)
        print(row, yy)
        if yy == -1:
            yy = self.maxY
        print(self.maxY, yy)
        y_max = min(self.maxY, yy)
        ret = []
        print(x_min, x_max, y_min, y_max)

        for y in chain(range(y_min, self.y), range(self.y+1, y_max+1)):
            ret.append(Move(self.x, y, self.step+1))
        for x in chain(range(x_min, self.x), range(self.x+1, x_max+1)):
            ret.append(Move(x, self.y, self.step+1))
        return re
def minimumMoves(grid, startX, startY, goalX, goalY):
    # Write your code here
    GameSetup.goalX = goalX
    GameSetup.goalY = goalY
    GameSetup.grid = grid
    moves = [Move(startX, startY, 0)]
    processed = set()
    
    while moves:
        move = heapq.heappop(moves)
        #move = moves[-1]
        print(f"current_{move=}")
        processed.add(tuple((move.x, move.y)))
        startX = move.x
        startY = move.y
        step = move.step
        if (startX, startY) == (goalX, goalY):
            return step
        next_moves = move.all_moves()
        valid_moves = [m for m in next_moves if m.cost < 1e9 and tuple((m.x, m.y)) not in processed]
        #valid_moves = sorted(valid_moves, reverse=True)
        for v in valid_moves:
            processed.add((v.x, v.y))
        moves.extend(valid_moves)
        heapq.heapify(moves)
        print(f"{moves=}")
        print(f"{processed=}"

public static int minimumMoves(List<String> grid, int startX, int startY, int goalX, int goalY) {       
				// We will assume the grid is filled and not empty
        // 1. Create a character matrix representing the SQUARE grid.
        int gridSize = grid.size();
        char[][] charGrid = new char[gridSize][gridSize];
        for (int i = 0; i < gridSize; i++) {
            for (int j = 0; j < gridSize; j++) {
                charGrid[i][j] = grid.get(i).charAt(j);
            }
        }

// 2. Implement BFS w/ a Queue. Point objects will be used to track valid cells.
        Queue<Point> queue = new LinkedList<>();
        // Create a "steps" matrix representing the steps to get to a cell in the grid.
        int[][] steps = new int[gridSize][gridSize];
        // Keep track of cells visited to avoid adding them to the Queue.
        boolean[][] visited = new boolean[gridSize][gridSize];
        // Add the starting point to the queue to start BFS.
        queue.add(new Point(startX, startY));
        visited[startX][startY] = true;
        
        while (!queue.isEmpty()) {
            Point current = queue.poll();
            // 3. We can move in 4 directions: Up (0), Right (1), Down (2), and Left (3).
            //    To represent these directions, refer to xMove and yMove.
            //    We will be adding to our queue the cells of each valid step in each 
            //    direction of our current cell.
            for (int i = 0; i < 4; i++) {
                // Used to explore the "adjacent" cells a certain valid distance from 
                // the current cell in each valid direction. 
                int distance = 1;
                // Check if the cell we are trying to "move" into is a valid cell.
                // A valid cell is a cell that is not an obstacle (X), and within bounds.
                while (isSafe(gridSize, current.x + xMove[i]*distance, current.y + 
                yMove[i]*distance, charGrid) && !visited[current.x + xMove[i]*distance]
                [current.y + yMove[i]*distance]) {
                    // Record the Point coordinates to be added into the queue.
                    int nextX = current.x + xMove[i]*distance;
                    int nextY = current.y + yMove[i]*distance;
                    visited[nextX][nextY] = true;
                    queue.add(new Point(nextX, nextY));
                    // Keep track of the "steps" taken to get to a cell.
                    steps[nextX][nextY] = steps[current.x][current.y] +1;
                    // Case where the point "adjacent" to current is the goal.
                    if (nextX == goalX && nextY == goalY) {
                        System.out.println(steps[nextX][nextY]);
                        return steps[nextX][nextY];
                    }
                    distance++;
                }
            }
        }
        
        // By default, return -1, indicating that the grid was not valid.
        return -1;
    }
		
 // Helper arrays used to define directions.
 // To move up (index 0): xMove is -1, yMove is 0.
 // To move right (index 1): xMove is 0, yMove is 1.
 // To move down (index 2): xMove is 1, yMove is 0.
 // To move left (index 3): xMove is 0, yMove is -1.
    private static int[] xMove = {-1, 0, 1, 0};
    private static int[] yMove = { 0, 1, 0, -1};
    
    // Private helper class to check if a step/move to a cell is valid in the grid.
    private static boolean isSafe (int gridSize, int x, int y, char[][] charGrid) {
        return (x >= 0 && 
                y >= 0 && 
                x < gridSize && 
                y < gridSize && 
                charGrid[x][y] == '.');
    }
}

// Private helper class used to instantiate "Point" objects
// A "Point" is used in the queue used to store valid moves from
// a current "Point"
class Point {
    public int x, y;
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
	
	

from collections import deque
def minimumMoves(grid, startX, startY, goalX, goalY):
    # Note: 
    # X means vertical direction in problem description's diagram
    # Y means horizontal direction in problem descritions's diagram
    # This is different with our habit. 
    # So I don't use the word left, right, up, or down in my code to avoid misleading names
    
    len_X = len(grid)
    len_Y = len(grid[0])
    visited = []
    for i in range(len_X):
        visited.append([False]*len_Y)
    
    queue = deque()
    # In the queue, each element is a tuple
    # Each tuple has 3 elements: x, y, and the number of moves from starting point to this location
    queue.append((startX, startY, 0))
    visited[startX][startY] = True
    while queue:
        cur_x, cur_y, cur_d = queue.popleft()
        
        if cur_x == goalX and cur_y == goalY:
            return cur_d
        
        #Add all potential moves toward smaller X
        for x in range(cur_x)[::-1]:
            if grid[x][cur_y] == '.' and not visited[x][cur_y]:
                queue.append((x,cur_y,cur_d+1))
                visited[x][cur_y] = True
            elif grid[x][cur_y] == 'X':
                break
                
        #Add all potential moves toward bigger X
        for x in range(cur_x,len_X):
            if grid[x][cur_y] == '.' and not visited[x][cur_y]:
                queue.append((x,cur_y,cur_d+1))
                visited[x][cur_y] = True
            elif grid[x][cur_y] == 'X':
                break
                
        #Add all potential moves toward smaller Y
        for y in range(cur_y)[::-1]:
            if grid[cur_x][y] == '.' and not visited[cur_x][y]:
                queue.append((cur_x,y,cur_d+1))
                visited[cur_x][y] = True
            elif grid[cur_x][y] == 'X':
                break
                
        #Add all potential moves toward bigger Y
        for y in range(cur_y,len_Y):
            if grid[cur_x][y] == '.' and not visited[cur_x][y]:
                queue.append((cur_x,y,cur_d+1))
                visited[cur_x][y] = True
            elif grid[cur_x][y] == 'X':
                break
    return -1   # The flag when the goal is not reachable