【AtCoder ABC453D】
グリッド探索でのDFS・BFS・状態の設計
（Common Lisp）

• グリッドBFSの基本は「座標を頂点、4方向への移動を辺」とするグラフ探索で、visited配列とprev配列の2つで「到達可能か」と「経路の復元」が書ける。
• 小さいグリッドは再帰DFSで書けるが、1000×1000のグリッドでは再帰が100万段深くなりスタックが溢れるため、キューを使うBFSに切り替える必要がある。
• 「直前の移動方向によって次の行動が変わる」制約があるとき、状態を(行, 列)から(行, 列, 方向)に拡張しないと、同じマスへの異なる到達経路が同一視されて探索が壊れる。
• 状態を拡張しても、コードの骨格は変わらない。
  visitedとprevの配列次元が増えて、遷移ルールにマスの種類ごとの分岐が加わるだけ。

1. グリッド探索問題

ABC453のD問題を題材にします。
H×Wのグリッドを移動して、スタートSからゴールGへ到達できるか判定し、できるなら経路を出力する問題です。

• D – Go Straight

2. 第1段階：小さいグリッドで再帰DFSを書く

まずはoとxのない単純なグリッドを、再帰で解いてみます。

全マスが. # S Gだけで、グリッドが小さい（H×W ≤ 10×10 程度）と仮定します。
.は自由に出入りでき、#は立ち入り禁止です。

2.1. 方向のキーワードシンボル

移動方向は、キーワードシンボル:up :down :left :rightで表現することにしました。

;;; 方向のキーワードシンボル
(defparameter *all-dirs* '(:up :down :left :right))

(declaim (inline dir->index dir->row dir->col dir->char))
(defun dir->index (dir)
  (ecase dir (:up 0) (:down 1) (:left 2) (:right 3)))

(defun dir->row (dir)
  (ecase dir (:up -1) (:down 1) (:left 0) (:right 0)))

(defun dir->col (dir)
  (ecase dir (:up 0) (:down 0) (:left -1) (:right 1)))

(defun dir->char (dir)
  (ecase dir (:up #\U) (:down #\D) (:left #\L) (:right #\R)))Code language: Lisp (lisp)

配列アクセスの直前だけdir->indexで整数に変換します。

2.2. 再帰による深さ優先探索(DFS)

再帰でのDFSは、シンプルに設計できます。

• 基底：現在地がゴールなら、成功
  グリッド外、#マス、訪問済みなら、失敗
• 再帰：4方向それぞれに進んでみて、成功したらそのパスを返す

(defun build-path-dfs (grid h w si sj gi gj)
  (let ((visited (make-array (list h w) :initial-element nil)))
    (labels ((rec (r c path)
               (cond
                 ((or (< r 0) (>= r h) (< c 0) (>= c w)) nil)
                 ((char= (aref grid r c) #\#) nil)
                 ((aref visited r c) nil)
                 ((and (= r gi) (= c gj)) (reverse path))
                 (t
                  (setf (aref visited r c) t)
                  (loop for dir in *all-dirs*
                        for result = (rec (+ r (dir->row dir))
                                         (+ c (dir->col dir))
                                         (cons (dir->char dir) path))
                        when result
                           do (return result))))))
      (rec si sj '()))))Code language: Lisp (lisp)

再帰DFSでは、通ったパスを自然に復元できます。
pathに移動文字を積みながら再帰して、ゴールに到達した瞬間にreverseで返すだけです。

2.3. DFSの動作を確認する

あとは、動作確認用の関数を作ります。

(defun verify-path (grid h w si sj gi gj path)
  "pathに従って移動した結果がゴールに到達するか検証する"
  (loop with r = si
        with c = sj
        for ch in path
        for dir = (ecase ch
                    (#\U :up) (#\D :down) (#\L :left) (#\R :right))
        do (setf r (+ r (dir->row dir))
                 c (+ c (dir->col dir)))
        finally (return (and (= r gi) (= c gj)))))Code language: Lisp (lisp)

小さなグリッドでチェックします。

(defparameter *grid* 
              (make-array '(3 3) :element-type 'character
                          :initial-contents '((#\S #\. #\.)
                                             (#\. #\# #\.)
                                             (#\. #\. #\G))))
(build-path-dfs *grid* 3 3 0 0 2 2)
;=> (#\D #\D #\R #\R)

(verify-path *grid* 3 3 0 0 2 2 (#\D #\D #\R #\R))
;=> T Code language: Lisp (lisp)

2.4. メイン関数

H行分の文字列を読み込み、文字をグリッドにセットします。

(defun read-grid (h w)
  (loop with grid = (make-array (list h w)
                                :element-type 'character
                                :initial-element #\#)
        with (si sj gi gj)  = '(-1 -1 -1 -1)
        for i from 0 below h
        for line = (read-line)
        do (loop for j from 0 below w
                 for ch = (char line j)
                 do (setf (aref grid i j) ch)
                 when (char= ch #\S) do (setf si i sj j)
                 when (char= ch #\G) do (setf gi i gj j))
        finally (return (values grid si sj gi gj))))Code language: Lisp (lisp)

とメイン関数を加えて完成です。

(defun main/dfs ()
  (let* ((h (read))
         (w (read)))
    (multiple-value-bind (grid si sj gi gj) (read-grid h w)
      (let ((result (build-path-dfs grid h w si sj gi gj)))
        (if result
            (format t "Yes~%~a~%" (coerce result 'string))
            (format t "No~%"))))))Code language: Lisp (lisp)

3. 第2段階：方向のあるDFS

ABC453のD問題では、oとxマスがありました。

これらは、来た方向によって進めない方向があるマスです。
oは直前と同じ方向にしか進めず、xは必ず方向を変えなければなりません。

たとえば、oマスに「右から来た場合」は右にしか進めませんが、「下から来た場合」は下にしか進めません。
座標だけで管理すると、「右から来たルート」で訪問済みにした瞬間に「下から来たルート」の行先が通れなくなってしまいます。

同じ座標でも、選択肢が変わることになります。
そこで、訪問済み判定で、来た方向が違えば別の状態として扱う必要があります。

3.1. 次の可能な方向（next-dirs）

新しい場所への移動は、方向制限を考慮する必要があります。
次に移動できる方向のリストは、マスの種類と直前の方向から決まるからです。

• . S G：4方向すべてに移動できる
• o：直前と同じ方向dirにしか移動できない
• x：直前と異なる方向にしか移動できない

next-dirs からセルと来た方向から有効な方向を返すように変更しています。

(defun next-dirs (cell dir)
  (cond
    ((char= cell #\o) (list dir))
    ((char= cell #\x) (remove dir *all-dirs*))
    (t *all-dirs*)))Code language: Lisp (lisp)

(remove dir *all-dirs*)は、新しいリストを生成しています。

3.2. 方向のある深さ優先探索（DFS）

;;; 方向ユーティリティ
(defparameter *all-dirs* '(:up :down :left :right))

(declaim (inline dir->index dir->row dir->col dir->char))
(defun dir->index (dir)
  (ecase dir (:up 0) (:down 1) (:left 2) (:right 3)))

(defun dir->row (dir)
  (ecase dir (:up -1) (:down 1) (:left 0) (:right 0)))

(defun dir->col (dir)
  (ecase dir (:up 0) (:down 0) (:left -1) (:right 1)))

(defun dir->char (dir)
  (ecase dir (:up #\U) (:down #\D) (:left #\L) (:right #\R)))

(defun build-path-dfs (grid h w si sj gi gj)
  (let ((visited (make-array (list h w) :initial-element nil)))
    (labels ((rec (r c path)
               (cond
                 ((or (< r 0) (>= r h) (< c 0) (>= c w)) nil)
                 ((char= (aref grid r c) #\#) nil)
                 ((aref visited r c) nil)
                 ((and (= r gi) (= c gj)) (reverse path))
                 (t
                  (setf (aref visited r c) t)
                  (loop for dir in *all-dirs*
                        for result = (rec (+ r (dir->row dir))
                                         (+ c (dir->col dir))
                                         (cons (dir->char dir) path))
                        when result
                           do (return result))))))
      (rec si sj '()))))

(defun read-grid (h w)
  (loop with grid = (make-array (list h w) :element-type 'character)
        with si = nil and sj = nil and gi = nil and gj = nil
        for i from 0 below h
        for row = (read-line)
        do (loop for j from 0 below w
                 for ch = (char row j)
                 do (setf (aref grid i j) ch)
                 when (char= ch #\S) do (setf si i sj j)
                 when (char= ch #\G) do (setf gi i gj j))
        finally (return (values grid si sj gi gj))))


(defun next-dirs (cell dir)
  (cond
    ((char= cell #\o) (list dir))
    ((char= cell #\x) (remove dir *all-dirs*))
    (t *all-dirs*)))

(defun build-path-dfs-with-dir (grid h w si sj gi gj)
  (let ((visited (make-array (list h w 4) :initial-element nil)))
    (labels ((rec (r c dir path)
               (cond
                 ((or (< r 0) (>= r h) (< c 0) (>= c w)) nil)
                 ((char= (aref grid r c) #\#) nil)
                 ((aref visited r c (dir->index dir)) nil)
                 ((and (= r gi) (= c gj)) (reverse path))
                 (t
                  (setf (aref visited r c (dir->index dir)) t)
                  (loop for nd in (next-dirs (aref grid r c) dir)
                        for result = (rec (+ r (dir->row nd))
                                         (+ c (dir->col nd))
                                         nd
                                         (cons (dir->char nd) path))
                        when result
                          do (return result))))))
      (loop for d in (remove :up *all-dirs*)
            do (setf (aref visited si sj (dir->index d)) t))
      (rec si sj :up '()))))

(defun main/dfs-with-dir ()
  (let* ((h (read))
         (w (read)))
    (multiple-value-bind (grid si sj gi gj) (read-grid h w)
      (let ((result (build-path-dfs-with-dir grid h w si sj gi gj)))
        (if result
            (format t "Yes~%~a~%" (coerce result 'string))
            (format t "No~%"))))))
#-swank(main/dfs-with-dir)Code language: PHP (php)

4. 第3段階：大きいグリッドではBFSに切り替える

H×Wが最大1000×1000のとき、再帰DFSは100万段の呼び出しが積み重なる可能性があります。
SBCLのデフォルトスタックでは確実に溢れます。
そこで、再帰を使わない実装が必要です。

BFSでは、再帰ではなくキューに状態を積んで繰り返し処理します。
骨格は同じですが、探索の順序が深さ優先から幅優先に変わります。

4.1. キューを用意する（queue）

キューは、先頭リストと末尾セルを同時に持つコンスセルで作ります。

;; queue
(declaim (inline make-queue enqueue dequeue queue-empty-p))
(defun make-queue ()
  (cons nil nil))

(defun enqueue (q x)
  (let ((cell (list x)))
    (if (car q)
        (setf (cdr (cdr q)) cell
              (cdr q) cell)
        (setf (car q) cell
              (cdr q) cell))))

(defun dequeue (q)
  (let ((cell (car q)))
    (when cell
      (prog1 (car cell)
        (setf (car q) (cdr cell))
        (unless (car q)
          (setf (cdr q) nil))))))

(defun queue-empty-p (q)
  (null (car q)))Code language: Lisp (lisp)

4.2. 移動先の列挙を追加する（expand）

現在地から遷移できる次の状態を列挙するexpandを作りました。

(defun expand (grid h w r c)
  (loop for nd in *all-dirs*
        for nr = (+ r (dir->row nd))
        for nc = (+ c (dir->col nd))
        when (and (>= nr 0) (< nr h)
                  (>= nc 0) (< nc w)
                  (char/= (aref grid nr nc) #\#))
          collect (list nr nc nd)))Code language: Lisp (lisp)

4.3. キューを使ったBFS（方向制限なし）

BFS本体です。

ゴールから逆順に辿るときに移動文字を取り出すために、prevには(前の行, 前の列, 移動した方向)の3つ組を保存します。

(defun build-path-bfs (grid h w si sj gi gj)
  (loop with visited = (make-array (list h w)
                                   :initial-element nil)
        with prev    = (make-array (list h w)
                                   :initial-element nil)
        with queue   = (make-queue)
          initially (setf (aref visited si sj) t)
                    (enqueue queue (list si sj))
        while (not (queue-empty-p queue))
        for cur = (dequeue queue)
        do (destructuring-bind (cr cc cd) cur
             (when (and (= cr gi) (= cc gj))
               (return (restore-path prev si sj gi gj)))
             (loop for (nr nc dir) in (expand grid h w cr cc)
                       unless (aref visited nr nc)
                         do (setf (aref visited nr nc) t)
                            (setf (aref prev nr nc) (list cr cc dir))
                            (enqueue queue (list (list nr nc)))))
        finally (return nil)))Code language: Lisp (lisp)

再帰DFSとの違いは、2つあります。
一つはrecの再帰呼び出しがqueueへの追加に変わること。
もう一つは、パスをpathに積む代わりにprev配列に「前の状態」を記録することです。

4.4. パスの復元とメイン関数（restore-path）

経路は、ゴール到達後にrestore-pathで復元します。
prev配列に「どこから来たか」を記録されているので、逆順に辿ります。

(defun restore-path (prev si sj gi gj)
  (loop with path = '()
        with cur  = (list gi gj)
        for row = (first cur)
        for col = (second cur)
        until (and (= row si) (= col sj))
        do (let* ((p (aref prev row col))
                 (dir (third p)))
             (push (dir->char dir) path)
             (setf cur p))
        finally (return path)))
Code language: Lisp (lisp)

メイン関数です。

(defun main/bfs ()
  (let* ((h (read))
         (w (read)))
    (multiple-value-bind (grid si sj gi gj) (read-grid h w)
      (let ((result (build-path-bfs grid h w si sj gi gj)))
        (if result
            (format t "Yes~%~a~%" (coerce result 'string))
            (format t "No~%"))))))Code language: Lisp (lisp)

5. 第5段階：BFSに方向を加える

5.1. 方向を加えた3つ組の状態を記録する（visited, prev）

visitedやprevに記録する状態を (行, 列, 直前の方向) の3つ組にし、3次元配列へのアクセス関数を用意しました。

(defun visited-p (visited r c dir)
  (aref visited r c (dir->index dir)))

(defun set-visited (visited r c dir)
  (setf (aref visited r c (dir->index dir)) t))

(defun get-prev (prev r c dir)
  (aref prev r c (dir->index dir)))

(defun set-prev (prev r c dir val)
  (setf (aref prev r c (dir->index dir)) val))Code language: Lisp (lisp)

5.2. 移動可能なマスを計算する（expand-with-dir）

expand-with-dir では、常に *all-dir*ではなくなりました。
next-dirs からセルと来た方向から有効な方向を返すように変更しています。

(defun expand-with-dir (grid h w r c dir)
  (loop for nd in (next-dirs (aref grid r c) dir)
        for nr = (+ r (dir->row nd))
        for nc = (+ c (dir->col nd))
        when (and (>= nr 0) (< nr h)
                  (>= nc 0) (< nc w)
                  (char/= (aref grid nr nc) #\#))
        collect (list nr nc nd)))Code language: Lisp (lisp)

5.3. 方向ありのBFS

BFS本体です。
スタート地点は直前の方向が存在しないので、4方向すべてを初期状態として積みます。

prevに入れる値に微妙だが重要な違いがあります。
(set-prev prev nr nc nd (list cr cc cd)) 。
このセルへの移動方向 nd ではなく、一つ前のセルに入ったときの 移動方向 cd です。

(defun build-path-bfs-with-dir (grid h w si sj gi gj)
  (loop with visited = (make-array (list h w 4)
                                   :initial-element nil)
        with prev    = (make-array (list h w 4)
                                   :initial-element nil)
        with queue   = (make-queue)
          initially (loop for dir in *all-dirs*
                          do (set-visited visited si sj dir)
                             (enqueue queue (list si sj dir)))
        while (not (queue-empty-p queue))
        for cur = (dequeue queue)
        do (destructuring-bind (cr cc cd) cur
             (when (and (= cr gi) (= cc gj))
               (return (restore-path-with-dir prev si sj cr cc cd)))
             (loop for (nr nc nd) in (expand-with-dir grid h w cr cc cd)
                   unless (visited-p visited nr nc nd)
                     do (set-visited visited nr nc nd)
                        (set-prev prev nr nc nd (list cr cc cd))
                        (enqueue queue (list nr nc nd))))
        finally (return nil)))Code language: Lisp (lisp)

build-path-bfs-simpleとの差分は2点だけです。
expandがexpand-with-dirに変わり、arefの直書きがvisited-p set-visited get-prev set-prevを通す形になります。

5.4. パス復元とメイン関数

パス復元も、方向を含めた prev の3次元配列から戻します。

(defun restore-path-with-dir (prev si sj gi gj goal-dir)
  (loop with path = '()
        with cur  = (list gi gj goal-dir)
        for row = (first cur)
        for col = (second cur)
        for dir = (third cur)
        until (and (= row si) (= col sj))
        do (let ((p (get-prev prev row col dir)))
              (push (dir->char dir) path)
              (setf cur p))
        finally (return path)))Code language: Lisp (lisp)

curは、ゴールから逆順で戻っていきます。

入力例1で確認します。

3 5
.#...
.Sooo
..x.GCode language: CSS (css)

;=> Yes
;=> DRUUDDRR  （または別の合法な経路）Code language: PHP (php)

メイン関数です。

(defun main/bfs-with-dir ()
  (let* ((h (read))
         (w (read)))
    (multiple-value-bind (grid si sj gi gj) (read-grid h w)
      (let ((result (build-path-bfs-with-dir grid h w si sj gi gj)))
        (if result
            (format t "Yes~%~a~%" (coerce result 'string))
            (format t "No~%"))))))Code language: Lisp (lisp)

5.5. 完成したコード（1893ms）

;;; 方向ユーティリティ
(defparameter *all-dirs* '(:up :down :left :right))

(declaim (inline dir->index dir->row dir->col dir->char))
(defun dir->index (dir)
  (ecase dir
    (:up 0) (:down 1) (:left 2) (:right 3)))

(defun dir->row (dir)
  (ecase dir
    (:up -1) (:down 1) (:left 0) (:right 0)))

(defun dir->col (dir)
  (ecase dir
    (:up 0) (:down 0) (:left -1) (:right 1)))

(defun dir->char (dir)
  (ecase dir
    (:up #\U) (:down #\D) (:left #\L) (:right #\R)))

;; queue
(declaim (inline make-queue enqueue dequeue queue-empty-p))
(defun make-queue ()
  (cons nil nil))

(defun enqueue (q x)
  (let ((cell (list x)))
    (if (car q)
        (setf (cdr (cdr q)) cell
              (cdr q) cell)
        (setf (car q) cell
              (cdr q) cell))))

(defun dequeue (q)
  (let ((cell (car q)))
    (when cell
      (prog1 (car cell)
        (setf (car q) (cdr cell))
        (unless (car q)
          (setf (cdr q) nil))))))

(defun queue-empty-p (q)
  (null (car q)))


;;; 3次元配列アクセス
(declaim (inline visited-p set-visited get-prev set-prev))
(defun visited-p (visited r c dir)
  (aref visited r c (dir->index dir)))

(defun set-visited (visited r c dir)
  (setf (aref visited r c (dir->index dir)) t))

(defun get-prev (prev r c dir)
  (aref prev r c (dir->index dir)))

(defun set-prev (prev r c dir val)
  (setf (aref prev r c (dir->index dir)) val))

;;; 遷移
(defun next-dirs (cell dir)
  (cond
    ((char= cell #\o) (list dir))
    ((char= cell #\x) (remove dir *all-dirs*))
    (t *all-dirs*)))

(defun expand-with-dir (grid h w r c dir)
  (loop for nd in (next-dirs (aref grid r c) dir)
        for nr = (+ r (dir->row nd))
        for nc = (+ c (dir->col nd))
        when (and (>= nr 0) (< nr h)
                  (>= nc 0) (< nc w)
                  (char/= (aref grid nr nc) #\#))
        collect (list nr nc nd)))


(defun build-path-bfs-with-dir (grid h w si sj gi gj)
  (loop with visited = (make-array (list h w 4)
                                   :initial-element nil)
        with prev    = (make-array (list h w 4)
                                   :initial-element nil)
        with queue   = (make-queue)
          initially (loop for dir in *all-dirs*
                          do (set-visited visited si sj dir)
                             (enqueue queue (list si sj dir)))
        while (not (queue-empty-p queue))
        for cur = (dequeue queue)
        do (destructuring-bind (cr cc cd) cur
             (when (and (= cr gi) (= cc gj))
               (return (restore-path-with-dir prev si sj cr cc cd)))
             (loop for (nr nc nd) in (expand-with-dir grid h w cr cc cd)
                   unless (visited-p visited nr nc nd)
                     do (set-visited visited nr nc nd)
                        (set-prev prev nr nc nd (list cr cc cd))
                        (enqueue queue (list nr nc nd))))
        finally (return nil)))

(defun restore-path-with-dir (prev si sj gi gj goal-dir)
  (loop with path = '()
        with cur  = (list gi gj goal-dir)
        for row = (first cur)
        for col = (second cur)
        for dir = (third cur)
        until (and (= row si) (= col sj))
        do (let ((p (get-prev prev row col dir)))
             (push (dir->char dir) path)
             (setf cur p))
        finally (return path)))

(defun read-grid (h w)
  (loop with grid = (make-array (list h w) :element-type 'character)
        with si = nil and sj = nil and gi = nil and gj = nil
        for i from 0 below h
        for row = (read-line)
        do (loop for j from 0 below w
                 for ch = (char row j)
                 do (setf (aref grid i j) ch)
                 when (char= ch #\S) do (setf si i sj j)
                 when (char= ch #\G) do (setf gi i gj j))
        finally (return (values grid si sj gi gj))))

(defun main ()
  (let* ((h (read))
         (w (read)))
    (multiple-value-bind (grid si sj gi gj) (read-grid h w)
      (let ((result (build-path-bfs-with-dir grid h w si sj gi gj)))
        (if result
            (format t "Yes~%~a~%" (coerce result 'string))
            (format t "No~%"))))))

#-swank(main)Code language: Lisp (lisp)

無事にクリアしました。
実行時間は、1893 msで、制限時間ギリギリですね。

6. 方向を数値で扱う（1542ms）

方向をキーワードではなく、数値で扱った版も作ってみました。
定数 +dr+ +dc+ +dir-char+ と 0-3 の値で値にアクセスします。

また、prev データに記録する情報を、その一つ前の向きだけにしました。
というのも、prev データを取得するときに、どの方法から来たのかはすでに持っているからです。

あと、queueをベクタ配列で持つようにしました。

(defconstant +dr+ #(-1  1  0  0))
(defconstant +dc+ #( 0  0 -1  1))
(defconstant +dir-char+ #(#\U #\D #\L #\R))

;; (next-dirs #\. 2)
(defun next-dirs/idx (cell dir)
  (ecase cell
    ((#\. #\S #\G) (list 0 1 2 3))
    (#\o (list dir))
    (#\x (remove dir '(0 1 2 3)))))

(defun expand-with-dir/idx (grid h w r c dir)
  (loop for nd in (next-dirs/idx (aref grid r c) dir)
        for nr = (+ r (aref +dr+ nd))
        for nc = (+ c (aref +dc+ nd))
        when (and (>= nr 0) (< nr h)
                  (>= nc 0) (< nc w)
                  (char/= (aref grid nr nc) #\#))
          collect (list nr nc nd)))

(defun build-path-bfs-with-dir/idx (grid h w si sj gi gj)
  (loop with visited = (make-array (list h w 4)
                                   :element-type 'boolean
                                   :initial-element nil)
        with prev = (make-array (list h w 4)
                                :element-type 'fixnum
                                :initial-element -2)
        with queue = (make-array 16 :adjustable t :fill-pointer 0)
        with queue-head = 0
          initially (loop for d in (list 0 1 2 3)
                          do (setf (aref visited si sj d) t))
                    (vector-push-extend (list si sj 0) queue)
        while (/= queue-head (fill-pointer queue))
        for cur = (aref queue queue-head)
        do (destructuring-bind (cr cc cd) cur
             (incf queue-head)
             (when (and (= cr gi) (= cc gj))
               (return (restore-path-with-dir/idx prev si sj cr cc cd)))
             (loop with cell = (aref grid cr cc)
                   for (nr nc nd) in (expand-with-dir/idx grid h w cr cc cd)
                   unless (aref visited nr nc nd)
                     do (setf (aref visited nr nc nd) t)
                        (setf (aref prev nr nc nd) cd)
                        (vector-push-extend (list nr nc nd) queue)))
        finally (return nil)))


;; -1 : start marker direction on prev table
(defun restore-path-with-dir/idx (prev si sj gi gj goal-dir)
  (loop with path = '()
        with row = gi
        with col = gj
        with dir = goal-dir
        for prev-dir = (aref prev row col dir) 
        until (and (= row si) (= col sj))
        do (push (aref +dir-char+ dir) path)
           (decf row (aref +dr+ dir))
           (decf col (aref +dc+ dir))
           (setf dir prev-dir)
        finally (return path)))

(defun read-grid (h w)
  (loop with grid = (make-array (list h w)
                                :element-type 'character
                                :initial-element #\#)
        with (si sj gi gj)  = '(-1 -1 -1 -1)
        for i from 0 below h
        for line = (read-line)
        do (loop for j from 0 below w
                 for ch = (char line j)
                 do (setf (aref grid i j) ch)
                 when (char= ch #\S) do (setf si i sj j)
                 when (char= ch #\G) do (setf gi i gj j))
        finally (return (values grid si sj gi gj))))

(defun main ()
  (let* ((h (read))
         (w (read)))
    (multiple-value-bind (grid si sj gi gj) (read-grid h w)
      (let ((path (build-path-bfs-with-dir/idx
                   grid h w si sj gi gj)))
        (if path
            (format t "Yes~%~a~%" (coerce path 'string))
            (format t "No~%"))))))

#-swank(main)
Code language: Lisp (lisp)

7. 状態設計の前後を比べる

段階ごとの差分をまとめます。

段階	状態	visitedの形	遷移の決め方	パス復元
再帰DFS	(r, c)	(h w) の2次元	expand	スタックから直接
BFS	(r, c)	(h w) の2次元	expand	restore-path
BFS＋方向	(r, c, dir)	(h w 4) の3次元	expand-with-dir	restore-path-with-dir

コードの骨格は変わりません。
状態の定義が変わると、配列の次元と遷移ルールだけが変わります。
「何を状態とするか」という設計の判断が、グラフ探索問題で最初に問われることです。