l = ["###############",
    "#...#...#.....#",
    "#.#.#.#.#.###.#",
    "#S#...#.#.#...#",
    "#######.#.#.###",
    "#######.#.#...#",
    "#######.#.###.#",
    "###..E#...#...#",
    "###.#######.###",
    "#...###...#...#",
    "#.#####.#.###.#",
    "#.#...#.#.#...#",
    "#.#.#.#.#.#.###",
    "#...#...#...###",
    "###############"]

with open('day20.txt') as f:
    l = f.read().splitlines()



def neighbours(l,x,y):
    neighb = []
    if l[x-1][y] == "." or l[x-1][y] == "E" :
        neighb.append((x-1,y))
    if l[x+1][y] == "." or l[x+1][y] == "E":
       neighb.append((x+1,y))
    if l[x][y-1] == "." or l[x][y-1] == "E":
       neighb.append((x,y-1))
    if l[x][y+1] == "." or l[x][y+1] == "E":
       neighb.append((x,y+1))
    return neighb

def in_bound(l,x,y):
    if x >= 1 and x <= len(l) - 2 :
        if y >= 1 and y <= len(l[0]) - 2 :
            return True
    return False

def is_wall(l,x,y):
    if (in_bound(l,x-1,y) and l[x-1][y]=="#") or (in_bound(l,x+1,y) and l[x+1][y]=="#"):
        if (in_bound(l,x,y-1) and l[x][y-1]=="#") or (in_bound(l,x,y+1) and l[x][y+1]=="#"):
            # print(x,y)
            return False
    if in_bound(l,x,y):
        return True
    


start = None
end = None
walls = []
path = []

for i in range(len(l)):
   for j in range(len(l[0])):
        if l[i][j] == "S":
            start = (i,j)
        elif l[i][j] == "E":
            end = (i,j)
        elif l[i][j] == "#" and is_wall(l,i,j):
            walls.append((i,j))

# print(in_bound(l,0,0))
# print(walls)


path.append(start)
# premier parcours 
print(end)
while path[-1]!=end:
    x,y = path[-1]
    neighb = neighbours(l,x,y)
    # print(x,y)
    for v in neighb:
        if v not in path:
            path.append(v)
    # print(path)
print(len(path))
print(len(walls))

# dmax = len(path)
shortcuts = {}

# for wall in walls:
#     xw,yw = wall
#     print(wall)
#     if (xw-1,yw) in path and (xw+1,yw) in path:
#         a,b = path.index((xw-1,yw)), path.index((xw+1,yw))
#         if a < b:
#             save = len(path[a:b]) - 2
#         else : 
#             save = len(path[b:a]) - 2
#         if save not in shortcuts.keys():
#             shortcuts[save] = 1
#         else :
#             shortcuts[save] += 1

#         # print(save)
#     elif (xw,yw-1) in path and (xw,yw+1) in path:
#         a,b = path.index((xw,yw-1)), path.index((xw,yw+1))
#         if a < b:
#             save = len(path[a:b]) - 2
#         else :
#             save = len(path[b:a]) - 2
#         if save not in shortcuts.keys():
#             shortcuts[save] = 1
#         else :
#             shortcuts[save] += 1
cnt = 0
for i in range(len(path)):
    x1,y1 = path[i]
    for j in range(i+1,len(path)):
        x2,y2 = path[j]
        d = abs(x2-x1) + abs(y2-y1)
        if d <= 20:
            save = j-i -d
            # if save not in shortcuts.keys():
            #     shortcuts[save] = 1
            # else :
            #     shortcuts[save] += 1
            if save >= 100 :
                cnt+=1

# print(save)
# print(shortcuts[50],shortcuts[52],shortcuts[54],shortcuts[76])
# print(shortcuts)
# cnt = 0
# for short in shortcuts.keys():
#     if short >= 100:
#         cnt += shortcuts[short]
print(cnt)

# queue = [(start, 0)]
# visited = set()

# while queue:
#   curr, dist = queue.pop()
#   x, y = curr

#   for xn, yn in neighbours(x, y):
#     if (xn, yn) in visited or not in_bound(xn, yn):
#         continue
#     queue.append(((xn,yn),dist+1))