def draw_maze(maze):
    '''Output the maze, and wait for the user to press <enter>.'''
    for row in maze:
        s = ''
        for ch in row:
            s += ch
        print s
    raw_input()

def valid_space(maze, r, c):
    '''Check if moving to (r,c) is a valid move in the maze; that is to say it
    is either a free square, or the exit.'''
    if 0 <= r < len(maze):
        if 0 <= c < len(maze[0]):
            if maze[r][c] in ' E':
                return True
    return False

def solve(maze, r, c):
    '''Recursively find a path from (r,c) to the exit.'''

    if maze[r][c] == 'E':
        # We have found the exit!
        return True
    
    if maze[r][c] == ' ':
        # Mark this position as being on our path.
        maze[r][c] = '*'
        
    draw_maze(maze)

    dr = [0, -1, 0, 1]
    dc = [-1, 0, 1, 0]

    for i in range(len(dr)):
        # Iterate over each possible direction.  To better understand this,
        # you may wish to unroll this loop.
        if valid_space(maze, r + dr[i], c + dc[i]):
            # If we aren't walking into a wall / visiting some square again...
            if solve(maze, r + dr[i], c + dc[i]):
                # If that move led us to the exit, then success!
                return True

    if maze[r][c] != 'S':
        # Backtrack from this move; leave a breadcrumb to indicate we are not
        # to search through this position again.
        maze[r][c] = '.'

    draw_maze(maze)

    return False


if __name__ == '__main__':
    # Read the maze from a file.
    fin = open('./maze.in', 'r')
    maze = []
    for line in fin:
        row = []
        line_strip = line.strip()
        for ch in line_strip:
            row.append(ch)
        maze.append(row)
    fin.close()

    draw_maze(maze)
    r = -1
    c = -1
    # Find start square.
    for x in range(len(maze)):
        for y in range(len(maze[0])):
            if maze[x][y] == 'S':
                r = x
                c = y
    # Start our search.
    solve(maze, r, c)