• + 0 comments
    #!/bin/python3
    
    import math
    import os
    import random
    import re
    import sys
    
    #
    # 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
    #
    
    from collections import deque
    
    def minimumMoves(grid, startX, startY, goalX, goalY):
        n = len(grid)
        m = len(grid[0])
        
        # Store visited cells to avoid cycles and redundant processing
        visited = set()
        
        # Queue stores tuples of (x, y, moves)
        queue = deque([(startX, startY, 0)])
        visited.add((startX, startY))
    
        while queue:
            x, y, moves = queue.popleft()
            
            if x == goalX and y == goalY:
                return moves
    
            # Define the four cardinal directions
            directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
            
            for dx, dy in directions:
                nx, ny = x, y
                
                # Slide as far as possible in the current direction
                while True:
                    nx += dx
                    ny += dy
                    
                    # Check bounds and for obstacles
                    if not (0 <= nx < n and 0 <= ny < m and grid[nx][ny] != 'X'):
                        break # Stop sliding if out of bounds or an obstacle is hit
                    
                    # Only add the final destination of the slide to the queue
                    if (nx, ny) not in visited:
                        visited.add((nx, ny))
                        queue.append((nx, ny, moves + 1))
        
        # Goal is unreachable
        return -1
    
    if __name__ == '__main__':
        fptr = open(os.environ['OUTPUT_PATH'], 'w')
    
        n = int(input().strip())
    
        grid = []
        for _ in range(n):
            grid.append(input())
    
        startX, startY, goalX, goalY = map(int, input().rstrip().split())
    
        result = minimumMoves(grid, startX, startY, goalX, goalY)
    
        fptr.write(str(result) + '\n')
    
        fptr.close()