Castle on the Grid

  • + 0 comments
    from collections import deque
    
    def minimumMoves(grid, startX, startY, goalX, goalY):
        # Initialize steps matrix with -1 for empty cells, -2 for obstacles
        steps = [[-1 if cell == '.' else -2 for cell in row] for row in grid]
        steps[startX][startY] = 0  # Start position has 0 steps
        
        # Initialize queue for BFS traversal
        dq = deque([(startX, startY)])
        
        # Define directions: UP, DOWN, LEFT, RIGHT
        directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]
        
        # Grid dimensions
        row, col = len(grid), len(grid[0])
        
        # Perform BFS
        while dq:
            x, y = dq.popleft()
            next_step = steps[x][y] + 1
            
            # Explore 4 directions
            for dx, dy in directions:
                i, j = x + dx, y + dy
                
                # Check boundary and obstacle conditions
                while 0 <= i < row and 0 <= j < col and steps[i][j] != -2:
                    if steps[i][j] == -1:  # If unvisited, mark with next step
                        steps[i][j] = next_step
                        dq.append((i, j))
                    else:  # If visited, update steps if new path is shorter
                        steps[i][j] = min(steps[i][j], next_step)
                    i, j = i + dx, j + dy
    
        return steps[goalX][goalY]  # Return steps to goal position