WITH RECURSIVE matrix AS MATERIALIZED (
  SELECT
    array_agg(regexp_split_to_array(line[1], '')) m
  FROM
    regexp_matches(
      $$
###############
#.......#....E#
#.#.###.#.###.#
#.....#.#...#.#
#.###.#####.#.#
#.#.#.......#.#
#.#.#####.###.#
#...........#.#
###.#.#####.#.#
#...#.....#.#.#
#.#.#.###.#.#.#
#.....#...#.#.#
#.###.#.#.#.#.#
#S..#.....#...#
###############
$$
    , '(?:^|[\r\n])(#[^\r\n]*#)(?=$|[\r\n])'
    , 'g'
    )
      WITH ORDINALITY y(line, y)
)
, poi AS MATERIALIZED (
  SELECT
    x
  , y
  , grpx
  , grpy
  FROM
    (
      SELECT
        *
      , sum(wall::integer) OVER(PARTITION BY x ORDER BY y) grpx -- группа по X
      , sum(wall::integer) OVER(PARTITION BY y ORDER BY x) grpy -- группа по Y
      FROM
        (
          SELECT
            x
          , y
          , m[y][x] = '#' wall
          FROM
            matrix
          , generate_subscripts(m, 1) y
          , generate_subscripts(m, 2) x
          WHERE
            m[y][x] IN ('S', 'E', '#') OR -- отбираем старт, финиш и все стены
            (
              m[y][x] = '.' AND -- проходные клетки отбираем только вне тоннеля
              (m[y][x - 1] <> '#' OR m[y][x + 1] <> '#') AND
              (m[y - 1][x] <> '#' OR m[y + 1][x] <> '#')
            )
        ) T
    ) T
  WHERE
    NOT wall -- стены нам не нужны
)
, stepline AS MATERIALIZED (
  SELECT
    x sx
  , y sy
  , array_remove(array_agg(x) OVER(PARTITION BY y, grpy), x) _tx
  , array_remove(array_agg(y) OVER(PARTITION BY x, grpx), y) _ty
  FROM
    poi
)
, segline AS MATERIALIZED (
  SELECT
    point(sx, sy)::text s        -- текстовое представление координат ячеек
  , point(tx, ty)::text t
  , CASE                         -- направление движения
      WHEN tx > sx THEN '(1,0)'  -- вправо
      WHEN tx < sx THEN '(-1,0)' -- влево
      WHEN ty > sy THEN '(0,1)'  -- вниз
      WHEN ty < sy THEN '(0,-1)' -- вверх
    END d
  , abs(tx - sx) + abs(ty - sy) score -- "стоимость" сегмента - разность координат
  FROM
    (
      SELECT
        sx
      , sy
      , unnest(_tx) tx -- возможные шаги по горизонтали
      , sy ty
      FROM
        stepline
    UNION ALL
      SELECT
        sx
      , sy
      , sx sy
      , unnest(_ty) ty -- возможные шаги по вертикали
      FROM
        stepline
    ) T
)
, dir AS MATERIALIZED (
  SELECT
    unnest(ARRAY[ -- направления "смотрения"
      '(1,0)'  -- вправо
    , '(0,1)'  -- вниз
    , '(-1,0)' -- влево
    , '(0,-1)' -- вверх
    ]::point[]) d
)
, onestep AS MATERIALIZED (
  SELECT
    point(x, y)::text s
  , ds.d::text ds
  , point(x, y)::text t
  , dt.d::text dt
  , 1000 score -- поворот на месте "за 1000"
  FROM
    poi
  , dir ds
  , dir dt
  WHERE
    dt.d[0] <> ds.d[0] AND -- это поворот, не разворот на 180
    dt.d[1] <> ds.d[1]
UNION ALL
  SELECT
    s
  , d ds
  , t
  , d dt
  , score     -- шаг по прямой к соседнему узлу
  FROM
    segline
)
, init AS MATERIALIZED (
  SELECT
    point(
      min(x) FILTER(WHERE m[y][x] = 'S')
    , min(y) FILTER(WHERE m[y][x] = 'S')
    )::text s -- координаты стартовой клетки
  , point(
      min(x) FILTER(WHERE m[y][x] = 'E')
    , min(y) FILTER(WHERE m[y][x] = 'E')
    )::text e -- координаты конечной клетки
  FROM
    matrix
  , generate_subscripts(m, 1) y
  , generate_subscripts(m, 2) x
  WHERE
    m[y][x] IN ('S', 'E')
)
, r AS (
  SELECT
    e                         -- протаскиваем целевую точку сквозь все шаги
  , s p                       -- текущая точка - стартовая
  , '(1,0)' d                 -- исходно смотрим направо
  , 0::bigint score           -- накопленная стоимость пути
  , FALSE turn                -- признак поворота на предыдущем шаге
  , ARRAY[s || ':(1,0)'] path -- уже достигнутый путь
  , FALSE fin                 -- признак достижения конечной точки на данном шаге
  FROM
    init
UNION ALL
  (
    WITH tmp AS (
      SELECT DISTINCT ON (state) -- уникализируем пути по достигнутому состоянию
        e
      , os.t p                   -- новая достигнутая точка
      , os.dt d                  -- новое направление
      , r.score + os.score score -- "стоимость" уже пройденного пути
      , os.t = os.s turn         -- признак поворота
      , r.path || state path
      FROM
        r
      JOIN
        onestep os
          ON (os.s, os.ds) = (r.p, r.d)
      , LATERAL (
          SELECT os.t || ':' || os.dt state -- состояние - это "куда пришли" + "куда смотрим"
        ) T
      WHERE
        p <> e AND             -- пока не пришли куда надо
        state <> ALL(path) AND -- исключаем зацикливание пути
        ( -- если на предыдущем шаге поворачивались, то на этом надо "шагать"
          NOT turn OR
          os.t <> os.s
        ) AND
        NOT fin                -- выход из рекурсии - достижение конечной точки
      ORDER BY
        state, r.score + os.score
    )
    SELECT
      *
    , bool_or(p = e) OVER() fin -- признак достижения конечной точки
    FROM
      tmp
  )
)
SELECT
  min(score)
FROM
  r
WHERE
  p = e;