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