#!/usr/bin/env python

import math
from collections import defaultdict

MAP = []
END = (0, 0)

def possible(x, y):
    global MAP

    threshold = MAP[y][x] + 1 # Can't go higher than this, can always go lower
    points = [(x-1,y),(x+1,y),(x,y-1),(x,y+1)]

    out = []
    for (x,y) in points:
        if x < 0 or y < 0:
            continue
        if len(MAP) < y+1 or len(MAP[y]) < x+1:
            continue
        if MAP[y][x] > threshold:
            continue
        out.append((x,y))
    return out

with open('input') as f:
    for y, line in enumerate(f):
        row = []
        for x, byte in enumerate(line.rstrip()):
            if byte == 'S':
                byte = 'a'
            elif byte == 'E':
                byte = 'z'
                END = (x,y)
            row.append(ord(byte) - ord('a'))
        MAP.append(row)

def search(start):
    distances = defaultdict(lambda: math.inf)
    distances[start] = 0
    visited = set([])
    queue = [start]

    while len(queue) > 0:
        pos = queue.pop(0)
        visited.add(pos)

        for neighbour in possible(*pos):
            if neighbour == END:
                return distances[pos] + 1

            if distances[neighbour] > distances[pos] + 1:
                distances[neighbour] = distances[pos] + 1

            if neighbour not in visited and neighbour not in queue:
                queue.append(neighbour)

    return None # Some start positions may not have a valid path

results = []
for y, row in enumerate(MAP):
    for x, height in enumerate(row):
        if height == 0:
            result = search((x,y))
            if result != None:
                results.append(result)

print(sorted(results)[0])