from collections import defaultdict
from heapq import heappush, heappop

def parse_maze(filename):
    with open(filename) as f:
        maze = [list(line.strip()) for line in f]
    
    # Find start and end
    start = end = None
    for y in range(len(maze)):
        for x in range(len(maze[0])):
            if maze[y][x] == 'S':
                start = (x, y)
            elif maze[y][x] == 'E':
                end = (x, y)
    return maze, start, end

def get_neighbors(pos, direction, maze):
    x, y = pos
    moves = []
    
    # Forward
    dx, dy = direction
    new_x, new_y = x + dx, y + dy
    if 0 <= new_x < len(maze[0]) and 0 <= new_y < len(maze) and maze[new_y][new_x] != '#':
        moves.append(((new_x, new_y), direction, 1))
    
    # Turn left
    new_dir = (-dy, dx)
    moves.append((pos, new_dir, 1000))
    
    # Turn right
    new_dir = (dy, -dx)
    moves.append((pos, new_dir, 1000))
    
    return moves

def find_min_score(maze, start, end):
    # Direction: (dx, dy)
    # Start facing east
    initial_dir = (1, 0)
    
    # Priority queue: (score, position, direction)
    queue = [(0, start, initial_dir)]
    seen = set()
    scores = defaultdict(lambda: float('inf'))
    scores[(start, initial_dir)] = 0
    
    while queue:
        score, pos, direction = heappop(queue)
        
        if pos == end:
            return score
            
        if (pos, direction) in seen:
            continue
        seen.add((pos, direction))
        
        for new_pos, new_dir, cost in get_neighbors(pos, direction, maze):
            new_score = score + cost
            if new_score < scores[(new_pos, new_dir)]:
                scores[(new_pos, new_dir)] = new_score
                heappush(queue, (new_score, new_pos, new_dir))
    
    return float('inf')

def find_optimal_paths(maze, start, end, min_score):
    optimal_tiles = set()
    initial_dir = (1, 0)
    
    def dfs(pos, direction, score, path):
        if score > min_score:
            return
        if pos == end and score == min_score:
            optimal_tiles.update(path)
            return
            
        for new_pos, new_dir, cost in get_neighbors(pos, direction, maze):
            if new_pos not in path or new_pos == end:  # Allow revisiting end
                dfs(new_pos, new_dir, score + cost, path | {new_pos})
    
    dfs(start, initial_dir, 0, {start})
    return len(optimal_tiles)

# Solve both parts
maze, start, end = parse_maze("input.txt")
min_score = find_min_score(maze, start, end)
print(str(min_score))
optimal_tiles = find_optimal_paths(maze, start, end, min_score)
print(str(optimal_tiles))