from itertools import product
import networkx as nx


def main():
    with open('d1.txt') as f:
        grid=[list(i) for i in f.read().split('\n')]

    height=len(grid)
    width=len(grid[0])

    for i,j in product(range(height),range(width)):
        if grid[i][j]=='S':
            start=(i,j)
        if grid[i][j]=='E':
            end=(i,j)

    G=nx.Graph()
    G.add_edge((start,(0,1)),(start,(-1,0)),weight=1000)
    for i,j in product(range(height),range(width)):
        if grid[i][j] in 'S#':
            continue
        if (i,j)==end:
            G.add_edge(((i+1,j),(-1,0)),end,weight=1)
            G.add_edge(((i,j-1),(0,1)),end,weight=1)
        for d in headings:
            x,y=move((i,j),d)

            if grid[x][y] not in 'E#':
                for d1 in headings:
                    dr=(-d[0],-d[1])
                    if d==d1:
                        continue
                    if dr==d1:
                        G.add_edge(((i,j),dr),((x,y),d1),weight=1)
                    else:
                        G.add_edge(((i,j),dr),((x,y),d1),weight=1001)

    print(nx.dijkstra_path_length(G,(start,(0,1)),end))

    seats=set()
    for l in nx.all_shortest_paths(G,(start,(0,1)),end,weight='weight',method='dijkstra'):
        s=map(lambda x:x[0],l)
        seats.update(s)
    print(len(seats))