from queue import PriorityQueue

DIRECTIONS = [(0, 1), (0, -1), (1, 0), (-1, 0)]

grid = [[c for c in line.strip()] for line in open("12.input")]

starts = []

for y, line in enumerate(grid):
    for x, c in enumerate(line):
        if c == 'S':
            start = (x, y)
            grid[y][x] = 'a'
        elif c == 'E':
            end = (x, y)
            grid[y][x] = 'z'
        elif c == 'a':
            starts.append((x, y))

size = (len(grid[0]), len(grid))

def nxt(pos):
    x, y = pos
    locs = []

    for (dx, dy) in DIRECTIONS:
        if 0 <= x + dx and x + dx < size[0]:
            if 0 <= y + dy and y + dy < size[1]:
                if ord(grid[y + dy][x + dx]) - ord(grid[y][x]) <= 1:
                    locs.append((x + dx, y + dy))

    return locs

def search(grid, start, end):
    dists = {}
    dists[start] = 0

    queue = PriorityQueue()
    queue.put((0, start))

    while not queue.empty():
        _, current = queue.get()
        dist = dists[current]
        if current == end:
            return dist
        for loc in nxt(current):
            old_dist = dists.get(loc, 1000000)
            if dist + 1 < old_dist:
                dists[loc] = dist + 1
                queue.put((dists[loc], loc))

    return 10000000

# Part 1
print(search(grid, start, end))

# Part 2, disgusting brute force. Could be done faster by inverting the
# neighbour condition and searching from 'end' to any of the positions in
# 'starts'.
print(min(search(grid, start, end) for start in starts))