(defstruct (queue (:constructor
		  $make-queue))
  arr
  start
  end)

(defun make-queue (size)
  ($make-queue :arr (make-array size :initial-element nil)
	       :start 0
	       :end 0))

(defun add-queue (queue obj)
  (setf (aref (queue-arr queue) (queue-end queue)) obj)
  (incf (queue-end queue)))

(defun null-queue (queue)
  "Gibt T zurück, wenn QUEUE leer ist."
  (= (queue-start queue) (queue-end queue)))

(defun get-queue (queue)
  (if (null-queue queue)
      (error "QUEUE is empty.")
      (prog1 (aref (queue-arr queue) (queue-start queue))
	(incf (queue-start queue)))))

(defun read-and-set-maze (maze height width)
  (dotimes (i height maze)
    (let ((line (read-line)))
      (dotimes (j width)
	(if (char= (aref line j) #\.)
	    (setf (aref maze i j) t)
	    (setf (aref maze i j) nil))))))

(defun get-connected-nodes (maze node)
  (let ((height (array-dimension maze 0))
	(width (array-dimension maze 1))
	(i (node-i node))
	(j (node-j node))
	(lst nil))
    (when (< 0 i)
      (push (make-node :i (- i 1) :j j :last node) lst))
    (when (< i (- height 1))
      (push (make-node  :i (+ i 1) :j j :last node) lst))
    (when (< 0 j)
      (push (make-node :i i :j (- j 1) :last node) lst))
    (when (< j (- width 1))
      (push (make-node :i i :j (+ j 1) :last node) lst))
    lst))


(defstruct node
  i j last)

(defun end-node-p (node maze)
  (and (= (node-i node) (- (array-dimension maze 0) 1))
       (= (node-j node) (- (array-dimension maze 1) 1))))

(defun already-checked-p (node table)
  (aref table (node-i node) (node-j node)))

(defun white-p (node maze)
  (aref maze (node-i node) (node-j node)))

(defun enum-nodes (node)
  (if (null (node-last node))
      1
      (1+ (enum-nodes (node-last node)))))

(defun enum-white (maze)
  (let ((sum 0))
    (dotimes (i (array-dimension maze 0))
      (dotimes (j (array-dimension maze 1))
	(when (aref maze i j)
	  (incf sum))))
    sum))

(defun enum-repainted (maze num-nodes)
  "Falls die Anzahl der Knoten im richtigen Weg NUM-NODES ist,
können wir die übrigen weißen Knoten übermalen, deren Anzahl (die
Anzahl der weißen Knoten - NUM-NODES) ist."
  (- (enum-white maze) num-nodes))
  
  
(defun search-path (maze)
  "Breitensuche. Gibt das letzte NODE zurück, falls vorhanden."
  (let* ((height (array-dimension maze 0))
	 (width (array-dimension maze 1))
	 (queue (make-queue (* height width)))
	 (table (make-array (list height width) :element-type 'boolean :initial-element nil)))
    (add-queue queue (make-node :i 0 :j 0 :last nil))
    (setf (aref table 0 0) t)
    (loop while (not (null-queue queue))
       do (let ((center-node (get-queue queue)))
	    (if (end-node-p center-node maze)
		(return center-node)
		(dolist (node (get-connected-nodes maze center-node))
		  (when (and (white-p node maze)
			     (not (already-checked-p node table)))
		    (add-queue queue node)
		    (setf (aref table (node-i node) (node-j node))
			  t)))))
       finally (return nil))))
    
    
(let* ((height (read))
       (width (read))
       (maze (make-array (list height width) :element-type 'boolean :initial-element nil)))      
  (read-and-set-maze maze height width)
  (let ((node (search-path maze)))
    (if node
	(format t "~A~%" (enum-repainted maze (enum-nodes (search-path maze))))
	(format t "~A~%" -1))))
  


Measured memory_bytes: 29156