import Data.Array

main :: IO ()
main = do
  input <- readFile "input"
  let grid = makeGrid (lines input)
  let start = head (findOnGrid grid 'S')
--  mapM_ print $ part1 grid start
  print $ part1 grid start

part1 grid start =
  let paths = runMaze grid [] [[start]]
--  in map (calcScore . reverse) paths
  in minimum $ map (calcScore . reverse) paths

calcScore path =
  let steps = zipWith (subPair) (tail path) path
      stepCost = zipWith (cmpDir) ((0,1):steps) steps
  in sum stepCost

subPair (a,b) (c,d) = (a-c,b-d)
cmpDir d1 d2
  | d1 == d2 = 1
  | otherwise = 1001

runMaze grid finished [] = finished
runMaze grid finished paths =
  let (next, fin) = unzip $ map (extendPath grid) paths
      (n, f) = (concat next, concat fin)
  in runMaze grid (finished ++ f) n

type Path = [(Int,Int)]
extendPath :: Grid -> Path -> ([Path], [Path])
extendPath grid path =
  let pos = head path
      neighbours = filter (`notElem` path) $ getNeighbours grid pos
      next = filter (\n -> grid!n == '.') neighbours
      end = filter (\n -> grid!n == 'E') neighbours
  in (map (\n->n:path) next,
      map (\n->n:path) end)

getNeighbours arr (i,j) = filter (inRange (bounds arr)) [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]

findOnGrid grid char = map fst . filter ((== char) . snd) . assocs $ grid

type Grid = Array (Int,Int) Char
makeGrid grid = array bounds elements
  where n = length grid
        m = length (head grid)
        bounds = ((0,0), (n-1,m-1))
        elements = [((i,j), (grid!!i!!j)) |
                    i <- [0..n-1], j <- [0..m-1]]