(ql:quickload '(fiveam))
(defpackage :day21
  (:use :cl :fiveam))
(in-package :day21)
;;22:55
;;23:32

(defun find-start (field)
  (destructuring-bind (rows cols)
      (array-dimensions field)
    (loop for row below rows do
      (loop for col below cols do
        (when (eq (aref field row col) #\S)
          (return-from find-start (list row col)))))))

(let* ((lines
         (uiop:read-file-lines "input"))
       (field (make-array (list (length lines) (length (car lines)))
                          :initial-contents lines))
       end-positions
       pending
       (start (find-start field))
       (visited (make-hash-table :test #'equal))
       )
  (push (cons 64 start) pending)
  (setf (gethash start visited) t)

  (destructuring-bind (rows cols)
      (array-dimensions field)
    (loop while pending
          for (steps-left row col) = (pop pending) do
            (when (zerop (mod steps-left 2))
              (push (list row col) end-positions))
            (unless (zerop steps-left)
              (loop
                for (dr dc) in '((0 1) (0 -1) (1 0) (-1 0))
                for nr = (+ row dr)
                for nc = (+ col dc)
                for new-pos = (list nr nc)
                when (and (< -1 nr rows)
                          (< -1 nc cols)
                          (not (eq #\# (aref field nr nc)))
                          (not (gethash new-pos visited)))
                  do (setf (gethash new-pos visited) t)
                     (push (cons (1- steps-left) new-pos) pending)))))
  ;; (list
  ;;  end-positions)
  ;; (length (remove-duplicates end-positions :test #'equal))
  (length
   end-positions)

  )