from bisect import insort
from typing import Optional


class Globals:
    start_position = None
    end_position = None


class Node:
    def __init__(self, position: tuple[int, int], previous_node: Optional["Node"], cost: int):
        self.position = position
        self.previous_node = previous_node
        self.cost = cost

        self.estimated_total_cost = cost + abs(Globals.end_position[0] - position[0]) + abs(
            Globals.end_position[1] - position[1])


def is_node_in_list(node_list: list[Node], position: tuple[int, int]):
    for node in node_list:
        if node.position == position:
            return True
    return False


data = []
with open("input") as f:
    for line in f:
        data.append(line.strip())

for row_idx, line in enumerate(data):
    for col_idx, char in enumerate(line):
        if char == "S":
            Globals.start_position = (row_idx, col_idx)
            if Globals.end_position is not None:
                break
        elif char == "E":
            Globals.end_position = (row_idx, col_idx)
            if Globals.start_position is not None:
                break
    else:
        continue
    break

row_count = len(data)
col_count = len(data[0])
traveled_to_positions = []
open_nodes = []
open_nodes.append(Node(Globals.start_position, None, 0))
while True:
    current_node = open_nodes.pop()
    if current_node.position == Globals.end_position:
        print(current_node.cost)
        break

    traveled_to_positions.append(current_node.position)
    if not current_node.previous_node is None:
        prev_pos = current_node.previous_node.position
        forward_dir = (current_node.position[0] - prev_pos[0], current_node.position[1] - prev_pos[1])
        came_from_dir = (forward_dir[0] * -1, forward_dir[1] * -1)
    else:
        came_from_dir = None
        forward_dir = (0, 1)
    for direct in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        if direct == came_from_dir:
            continue

        is_forward_dir = forward_dir == direct

        new_pos = (current_node.position[0] + direct[0], current_node.position[1] + direct[1])
        if 0 <= new_pos[0] < row_count and 0 <= new_pos[1] < col_count and data[new_pos[0]][new_pos[1]] != "#" and \
                new_pos not in traveled_to_positions and not is_node_in_list(open_nodes, new_pos):
            new_node = Node(new_pos, current_node, current_node.cost + (1 if is_forward_dir else 1001))
            insort(open_nodes, new_node, key=lambda x: -x.estimated_total_cost)