#!/usr/bin/python
from operator import add, neg

SKIP = -1
SOLID = 0
OK = 1
PATH = 2

NONE = 0
START = 1
END = 2

KEY = { # (top, bot, status)
    '\n': (SKIP, SKIP, NONE),
    'S': (OK, OK, START),
    'E': (OK, OK, END),
    ' ': (OK, OK, NONE),
    '.': (OK, SOLID, NONE),
    '_': (OK, SOLID, NONE),
    '|': (SOLID, SOLID, NONE),
}

DIRS = {
    'N': (0, -1),
    'S': (0, 1),
    'E': (1, 0),
    'W': (-1, 0),
}

PRINT = {
    SOLID: 'x',
    OK: ' ',
    PATH: '.',
}

class Maze():

    def __init__(self, string):
        self.maze = []
        for y, line in enumerate(string.split('\n')):
            prev = []
            cur = []
            for x, char in enumerate(line):
                prev += [KEY[char][0]]
                cur += [KEY[char][1]]

                if KEY[char][2] == START:
                    self.start = (x, y*2)
                elif KEY[char][2] == END:
                    self.end = (x, y*2)
            self.maze += ([prev] if y else []) + [cur]

    def inmaze(self, coord):
        return 0 <= coord[0] < len(self.maze[0]) and \
               0 <= coord[1] < len(self.maze)

    def cango(self, coord):
        return self.maze[coord[1]][coord[0]]

    def go(self, src, to, path):
        # Invalid?
        if not self.inmaze(to) or not self.cango(to):
            return []

        path += [to]

        # Reached the end?
        if to == self.end:
            return path

        try:
            # Check everywhere else
            return next(future for future in [
                self.go(DIRS[key], tuple(map(add, DIRS[key], to)), path[:])
                for key in DIRS if tuple(map(neg, DIRS[key])) != src
            ] if future)
        except StopIteration:
            # No answer
            return []

    @property
    def solution(self):
        return self.go(None, self.start, [])

    @property
    def solved_maze(self):
        result = self.maze[:]
        for coord in self.solution:
            result[coord[1]][coord[0]] = PATH
        return result

    def print_solved(self):
        print '\n'.join(
            [' '.join(
                [PRINT[val] for val in line]
            ) for line in self.solved_maze]
        )

Maze(''.join(open('maze.txt', 'r').readlines())).print_solved()