from heapq import heappush, heappop
from itertools import count

DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1))

def distance(a, b):
    return sum(abs(x - y) for x, y in zip(a, b))

def astar_path(G, source, target, heuristic):
    n, m = len(G), len(G[0])
    push = heappush
    pop = heappop

    c = count()
    queue = [(0, next(c), source, 0, None)]

    enqueued = {}
    explored = {}

    while queue:
        _, __, curnode, dist, parent = pop(queue)
        if curnode == target:
            path = [curnode]
            node = parent
            while node is not None:
                path.append(node)
                node = explored[node]
            path.reverse()
            return path

        if curnode in explored:
            if explored[curnode] is None:
                continue

            qcost, h = enqueued[curnode]
            if qcost < dist:
                continue

        explored[curnode] = parent
        x, y = curnode
        neighbors = [(x + dx, y + dy) for dx, dy in DIRS if 0 <= x + dx < n and 0 <= y + dy < m and G[x + dx][y + dy] in '~t']
        
        for neighbor in neighbors:
            ncost = dist + 1
            if neighbor in enqueued:
                qcost, h = enqueued[neighbor]
                if qcost <= ncost:
                    continue
            else:
                h = heuristic(neighbor, target)
            enqueued[neighbor] = ncost, h
            push(queue, (ncost + h, next(c), neighbor, ncost, curnode))

    return None

def solve(s):
    grid = [list (x) for x in s.split('\n')]
    G = {}
    sharks, jellys, urchins = set(), set(), set()
    n, m = len(grid), len(grid[0])
    for i in range(n):
        for j in range(m):
            if grid[i][j] == 'e':
                sx, sy = i, j
            elif grid[i][j] == 't':
                tx, ty = i, j
            elif grid[i][j] == 'S':
                sharks.add((i, j))
            elif grid[i][j] == 'Y':
                jellys.add((i, j))
            elif grid[i][j] == 'O':
                urchins.add((i, j))
    obs = set()
    for x, y in sharks:
        ny = y
        while 1:
            if ny >= m or grid[x][ny] in '#.':
                break
            obs.add((x, ny))
            ny += 1
        ny = y
        while 1:
            if ny < 0 or grid[x][ny] in '#.':
                break            
            obs.add((x, ny))
            ny -= 1
    for x, y in jellys:
        nx = x
        while 1:
            if nx >= n or grid[nx][y] in '#.':
                break
            obs.add((nx, y))
            nx += 1
        nx = x
        while 1:
            if nx < 0 or grid[nx][y] in '#.':
                break
            obs.add((nx, y))
            nx -= 1
    for x, y in urchins:
        for dx in range(-1, 2):
            for dy in range(-1, 2):
                u, v = x + dx, y + dy
                if 0 <= u < n and 0 <= v < m:
                    obs.add((u, v))
    for x, y in obs:
        grid[x][y] = '#'
    return astar_path(grid, (sx, sy), (tx, ty), distance)

    
grids = [
    '....................\n....................\n~~~~~~~~~~##~~~~~~~~\n~~t~~~~~~####~~~~~~~\n~~~~~~~~######~~~e~~',
    '~~~~~~~~~~~~~~~e~~~~\n~~~~###~~~~~S~~~~~~~\n~~~~~~~~~~~~~~#~~~~~\n~S~~~~S~~~#~~##~~~S~\n~~~~~~~~~~~~~~~~~t~~',
    '~~~~e~~#~~~~~~~~~Y~~\n~~Y~~~~~~~####~Y~~~~\n~~Y~~Y~Y~~~~~~~Y~#~~\n~~~~~#~#~~Y~~~~#~~~~\n~Y~~~~~~~~~~~~~~~t~~'
]


for s in grids:
    r = solve(s)
    print(r)