#First, build the neighborhood of nodes: for a given position, move in all directions and add possible nodes to the adjacency list
# Then, do a BFS from start node, until we reach end node, count how many levels of BFS traversal needed 

from collections import defaultdict, deque
def check_go(i, j, d_i, d_j, grid, ngbs_ij):
    n = len(grid)
    cur_i = i + d_i
    cur_j = j + d_j
    while 0 <= cur_i < n and 0 <= cur_j < n and grid[cur_i][cur_j]=='.':
        ngbs_ij.append((cur_i, cur_j))
        cur_i += d_i
        cur_j += d_j
        
def build_ngbs(grid):
    ngbs = defaultdict(list)
    n = len(grid)
    for i in range(n):
        for j in range(n):
            if grid[i][j] == '.':
                #check ngbs
                check_go(i, j, 0, -1, grid, ngbs[(i,j)])
                check_go(i, j, 0, +1, grid, ngbs[(i,j)])
                check_go(i, j, -1, 0, grid, ngbs[(i,j)])
                check_go(i, j, +1, 0, grid, ngbs[(i,j)])
    return ngbs  
                

def minimumMoves(grid, startX, startY, goalX, goalY):
    ngbs = build_ngbs(grid)
    q = deque()
    visited = set()
    q.append((startX, startY))
    visited.add((startX, startY))
    level_counter = -1
    while q:
        level_size = len(q)
        level_counter+=1
        for _ in range(level_size):
            node = q.popleft()
            if node==(goalX, goalY):
                return level_counter
            for neighbor in ngbs[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    q.append(neighbor)

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