# Input: grid of # . S E
# Output: how many cheating paths (two consecutive steps allowed to hit #)
#           get from S to E (UDLR) at least 100 steps faster than non-cheating?
#         a cheat is identified by its start position (before the first #)
#           and end position

grid = []

sr, sc, er, ec = -1, -1, -1, -1

r = 0
file = open("20_input.txt", "r")
for line in file:
  line = line.replace("\n", "")
  row = []
  c = 0
  for character in line:
    if character == "S":
      sr, sc = r, c
      character = "."
    if character == "E":
      er, ec = r, c
      character = "."
    row.append(character)
    c += 1
  grid.append(row)
  r += 1

distance_from_start = []
distance_from_end = []
for r in range(len(grid)):
  row = [-1] * len(grid[0])
  distance_from_start.append(row)
  row = [-1] * len(grid[0])
  distance_from_end.append(row)
distance_from_start[sr][sc] = 0
distance_from_end[er][ec] = 0

cells_from_start = [[sr, sc]]
while len(cells_from_start) > 0:
  cell = cells_from_start[0]
  cells_from_start = cells_from_start[1:]
  distance = distance_from_start[cell[0]][cell[1]]
  nr, nc = cell[0] - 1, cell[1]
  if grid[nr][nc] == ".":
    if distance_from_start[nr][nc] == -1 or distance_from_start[nr][nc] > distance + 1:
      distance_from_start[nr][nc] = distance + 1
      cells_from_start.append([nr, nc])
  nr, nc = cell[0] + 1, cell[1]
  if grid[nr][nc] == ".":
    if distance_from_start[nr][nc] == -1 or distance_from_start[nr][nc] > distance + 1:
      distance_from_start[nr][nc] = distance + 1
      cells_from_start.append([nr, nc])
  nr, nc = cell[0], cell[1] - 1
  if grid[nr][nc] == ".":
    if distance_from_start[nr][nc] == -1 or distance_from_start[nr][nc] > distance + 1:
      distance_from_start[nr][nc] = distance + 1
      cells_from_start.append([nr, nc])
  nr, nc = cell[0], cell[1] + 1
  if grid[nr][nc] == ".":
    if distance_from_start[nr][nc] == -1 or distance_from_start[nr][nc] > distance + 1:
      distance_from_start[nr][nc] = distance + 1
      cells_from_start.append([nr, nc])

cells_from_end = [[er, ec]]
while len(cells_from_end) > 0:
  cell = cells_from_end[0]
  cells_from_end = cells_from_end[1:]
  distance = distance_from_end[cell[0]][cell[1]]
  nr, nc = cell[0] - 1, cell[1]
  if grid[nr][nc] == ".":
    if distance_from_end[nr][nc] == -1 or distance_from_end[nr][nc] > distance + 1:
      distance_from_end[nr][nc] = distance + 1
      cells_from_end.append([nr, nc])
  nr, nc = cell[0] + 1, cell[1]
  if grid[nr][nc] == ".":
    if distance_from_end[nr][nc] == -1 or distance_from_end[nr][nc] > distance + 1:
      distance_from_end[nr][nc] = distance + 1
      cells_from_end.append([nr, nc])
  nr, nc = cell[0], cell[1] - 1
  if grid[nr][nc] == ".":
    if distance_from_end[nr][nc] == -1 or distance_from_end[nr][nc] > distance + 1:
      distance_from_end[nr][nc] = distance + 1
      cells_from_end.append([nr, nc])
  nr, nc = cell[0], cell[1] + 1
  if grid[nr][nc] == ".":
    if distance_from_end[nr][nc] == -1 or distance_from_end[nr][nc] > distance + 1:
      distance_from_end[nr][nc] = distance + 1
      cells_from_end.append([nr, nc])

total = 0
non_cheat_time = distance_from_start[er][ec]
for r in range(len(grid)):
  for c in range(len(grid[0])):
    if grid[r][c] == ".":
      for dr in range(-2, 3):
        for dc in range(-2, 3):
          if abs(dr) + abs(dc) == 2:
            nr, nc = r + dr, c + dc
            if nr >= 0 and nr < len(grid) and nc >= 0 and nc < len(grid):
              if grid[nr][nc] == ".":
                # skip paths that overshoot the goal
                if dr == 0 and c < ec and nc > ec:
                  continue
                if dr == 0 and c > ec and nc < ec:
                  continue
                if dc == 0 and r > er and nr < er:
                  continue
                if dc == 0 and r < er and nr > er:
                  continue
                # skip paths whose first cheat step isn't a cheat
                if dr == 0 and grid[r][c + int(dc/2)] == ".":
                  continue
                if dc == 0 and grid[r + int(dr/2)][c] == ".":
                  continue
                savings = non_cheat_time - (distance_from_start[r][c] + 2 + distance_from_end[nr][nc])
                if savings >= 100:
                  total += 1
print (total)