from collections import deque
from common import day

with open(f"input/{day()}") as fh:
    G = [line.rstrip() for line in fh]

for i, s in enumerate(G):
    if (j := s.find("S")) != -1:
        start = (i, j)
    if (j := s.find("E")) != -1:
        end = (i, j)

def elevation(s):
    if s == "S":
        return 0
    if s == "E":
        return 25
    else:
        return ord(s) - 97

def get_neighbours(G, pos):
    m, n = len(G), len(G[0])
    i, j = pos
    g = [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]
    g = filter(lambda t: (0 <= t[0] < m) and (0 <= t[1] < n), g)
    return filter(lambda p: elevation(G[p[0]][p[1]]) <= elevation(G[i][j]) + 1, g)


def bfs(start, end, G, visited):
    q = deque()
    q.append(start)
    visited[start] = None
    while q:
        v = q.popleft()
        if v == end:
            return visited
        else:
            for w in get_neighbours(G, v):
                if w not in visited:
                    q.append(w)
                    visited[w] = v

curr_min = 484
for i in range(len(G)):
    for j in range(len(G[0])):
        if G[i][j] == "a":
            visited = {}
            start = (i, j)
            pomme = bfs(start, end, G, visited)
            if pomme is None:
                continue
            path = [end]
            parent = end
            while True:
                parent = visited[parent]
                if parent is None:
                    break
                path.append(parent)
            curr_min = min(curr_min, len(path) -1)

print(curr_min)