(defun zigzag-scan (ary &optional (fn (lambda (&key subscripts
                                                    index
                                                    nth
                                                    direction
                                                    element)
                                        (list :nth nth
                                              :element element
                                              :subscripts subscripts
                                              :index index
                                              :direction direction)))
                        &aux (northern-end 0)
                             (eastern-end (1- (cadr (array-dimensions ary))))
                             (southern-end (1- (car (array-dimensions ary))))
                             (western-end 0))
  (let ((result '())
        (nth 0)
        (x 0)
        (y 0)
        (dir (if (and (= western-end eastern-end)
                      (/= northern-end southern-end))
                 'S 'E)))
    (loop
      (push (funcall fn
                     :nth nth
                     :element (aref ary y x)
                     :subscripts (list y x)
                     :index (array-row-major-index ary y x)
                     :direction dir)
            result)
 
      (incf nth)
 
      ;; 右下隅に到達したら終了。
      (when (and (= y southern-end)
                 (= x eastern-end))
        (return (nreverse result)))
 
      ;; 移動する。
      (ecase dir
        (E (incf x))
        (S (incf y))
        (SW (decf x) (incf y))
        (NE (incf x) (decf y)))
 
      ;; 次に移動する方向を設定する。
      (setf dir
            (or (ecase dir
                  (E  (cond ((= y northern-end southern-end) 'E)
                            ((= x western-end eastern-end)   'S)
                            ((= y southern-end)              'NE)
                            (t                               'SW)))
                  (S  (cond ((= x western-end eastern-end)               'S)
                            ((and (= x eastern-end) (= y southern-end)   'NE))
                            ((= x western-end)                           'NE)
                            (t                                           'SW)))
                  (SW (cond ((and (= x western-end) (/= y southern-end)) 'S)
                            ((= y southern-end)                          'E)))
                  (NE (cond ((and (= y northern-end) (= x eastern-end))  'S)
                            ((= x eastern-end)                           'S)
                            ((= y northern-end)                          'E))))
                dir)))))
 
(loop for (M N) in '((3 3) (4 2) (3 5) (1 8) (9 11))
      do (let* ((A (make-array (list M N)))
                (path (zigzag-scan A)))
           (loop initially (format t "~D ~D~%"
                                   (first (array-dimensions A))
                                   (second (array-dimensions A)))
                 finally (format t "~2%")
                 with width = (second (array-dimensions A))
 
                 for sq in (sort path #'< :key (lambda (sq) (getf sq :index)))
 
                 for index from 0
                 when (zerop (mod index width))
                   do (fresh-line)
 
                 do (format t "~2D~@{~A~}"
                            (1+ (getf sq :nth))
                            (ecase (getf sq :direction)
                              (N #\↑) (NE #\↗) (E #\→) (SE #\↘)
                              (S #\↓) (SW #\↙) (W #\←) (NW #\↖))))))
 

KGRlZnVuIHppZ3phZy1zY2FuIChhcnkgJm9wdGlvbmFsIChmbiAobGFtYmRhICgma2V5IHN1YnNjcmlwdHMKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGluZGV4CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBudGgKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGRpcmVjdGlvbgogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgZWxlbWVudCkKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIChsaXN0IDpudGggbnRoCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICA6ZWxlbWVudCBlbGVtZW50CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICA6c3Vic2NyaXB0cyBzdWJzY3JpcHRzCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICA6aW5kZXggaW5kZXgKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIDpkaXJlY3Rpb24gZGlyZWN0aW9uKSkpCiAgICAgICAgICAgICAgICAgICAgICAgICZhdXggKG5vcnRoZXJuLWVuZCAwKQogICAgICAgICAgICAgICAgICAgICAgICAgICAgIChlYXN0ZXJuLWVuZCAoMS0gKGNhZHIgKGFycmF5LWRpbWVuc2lvbnMgYXJ5KSkpKQogICAgICAgICAgICAgICAgICAgICAgICAgICAgIChzb3V0aGVybi1lbmQgKDEtIChjYXIgKGFycmF5LWRpbWVuc2lvbnMgYXJ5KSkpKQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICh3ZXN0ZXJuLWVuZCAwKSkKICAobGV0ICgocmVzdWx0ICcoKSkKICAgICAgICAobnRoIDApCiAgICAgICAgKHggMCkKICAgICAgICAoeSAwKQogICAgICAgIChkaXIgKGlmIChhbmQgKD0gd2VzdGVybi1lbmQgZWFzdGVybi1lbmQpCiAgICAgICAgICAgICAgICAgICAgICAoLz0gbm9ydGhlcm4tZW5kIHNvdXRoZXJuLWVuZCkpCiAgICAgICAgICAgICAgICAgJ1MgJ0UpKSkKICAgIChsb29wCiAgICAgIChwdXNoIChmdW5jYWxsIGZuCiAgICAgICAgICAgICAgICAgICAgIDpudGggbnRoCiAgICAgICAgICAgICAgICAgICAgIDplbGVtZW50IChhcmVmIGFyeSB5IHgpCiAgICAgICAgICAgICAgICAgICAgIDpzdWJzY3JpcHRzIChsaXN0IHkgeCkKICAgICAgICAgICAgICAgICAgICAgOmluZGV4IChhcnJheS1yb3ctbWFqb3ItaW5kZXggYXJ5IHkgeCkKICAgICAgICAgICAgICAgICAgICAgOmRpcmVjdGlvbiBkaXIpCiAgICAgICAgICAgIHJlc3VsdCkKCiAgICAgIChpbmNmIG50aCkKCiAgICAgIDs7IOWPs+S4i+maheOBq+WIsOmBlOOBl+OBn+OCiee1guS6huOAggogICAgICAod2hlbiAoYW5kICg9IHkgc291dGhlcm4tZW5kKQogICAgICAgICAgICAgICAgICg9IHggZWFzdGVybi1lbmQpKQogICAgICAgIChyZXR1cm4gKG5yZXZlcnNlIHJlc3VsdCkpKQoKICAgICAgOzsg56e75YuV44GZ44KL44CCCiAgICAgIChlY2FzZSBkaXIKICAgICAgICAoRSAoaW5jZiB4KSkKICAgICAgICAoUyAoaW5jZiB5KSkKICAgICAgICAoU1cgKGRlY2YgeCkgKGluY2YgeSkpCiAgICAgICAgKE5FIChpbmNmIHgpIChkZWNmIHkpKSkKCiAgICAgIDs7IOasoeOBq+enu+WLleOBmeOCi+aWueWQkeOCkuioreWumuOBmeOCi+OAggogICAgICAoc2V0ZiBkaXIKICAgICAgICAgICAgKG9yIChlY2FzZSBkaXIKICAgICAgICAgICAgICAgICAgKEUgIChjb25kICgoPSB5IG5vcnRoZXJuLWVuZCBzb3V0aGVybi1lbmQpICdFKQogICAgICAgICAgICAgICAgICAgICAgICAgICAgKCg9IHggd2VzdGVybi1lbmQgZWFzdGVybi1lbmQpICAgJ1MpCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAoKD0geSBzb3V0aGVybi1lbmQpICAgICAgICAgICAgICAnTkUpCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAodCAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAnU1cpKSkKICAgICAgICAgICAgICAgICAgKFMgIChjb25kICgoPSB4IHdlc3Rlcm4tZW5kIGVhc3Rlcm4tZW5kKSAgICAgICAgICAgICAgICdTKQogICAgICAgICAgICAgICAgICAgICAgICAgICAgKChhbmQgKD0geCBlYXN0ZXJuLWVuZCkgKD0geSBzb3V0aGVybi1lbmQpICAgJ05FKSkKICAgICAgICAgICAgICAgICAgICAgICAgICAgICgoPSB4IHdlc3Rlcm4tZW5kKSAgICAgICAgICAgICAgICAgICAgICAgICAgICdORSkKICAgICAgICAgICAgICAgICAgICAgICAgICAgICh0ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICdTVykpKQogICAgICAgICAgICAgICAgICAoU1cgKGNvbmQgKChhbmQgKD0geCB3ZXN0ZXJuLWVuZCkgKC89IHkgc291dGhlcm4tZW5kKSkgJ1MpCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAoKD0geSBzb3V0aGVybi1lbmQpICAgICAgICAgICAgICAgICAgICAgICAgICAnRSkpKQogICAgICAgICAgICAgICAgICAoTkUgKGNvbmQgKChhbmQgKD0geSBub3J0aGVybi1lbmQpICg9IHggZWFzdGVybi1lbmQpKSAgJ1MpCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAoKD0geCBlYXN0ZXJuLWVuZCkgICAgICAgICAgICAgICAgICAgICAgICAgICAnUykKICAgICAgICAgICAgICAgICAgICAgICAgICAgICgoPSB5IG5vcnRoZXJuLWVuZCkgICAgICAgICAgICAgICAgICAgICAgICAgICdFKSkpKQogICAgICAgICAgICAgICAgZGlyKSkpKSkKCihsb29wIGZvciAoTSBOKSBpbiAnKCgzIDMpICg0IDIpICgzIDUpICgxIDgpICg5IDExKSkKICAgICAgZG8gKGxldCogKChBIChtYWtlLWFycmF5IChsaXN0IE0gTikpKQogICAgICAgICAgICAgICAgKHBhdGggKHppZ3phZy1zY2FuIEEpKSkKICAgICAgICAgICAobG9vcCBpbml0aWFsbHkgKGZvcm1hdCB0ICJ+RCB+RH4lIgogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIChmaXJzdCAoYXJyYXktZGltZW5zaW9ucyBBKSkKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAoc2Vjb25kIChhcnJheS1kaW1lbnNpb25zIEEpKSkKICAgICAgICAgICAgICAgICBmaW5hbGx5IChmb3JtYXQgdCAifjIlIikKICAgICAgICAgICAgICAgICB3aXRoIHdpZHRoID0gKHNlY29uZCAoYXJyYXktZGltZW5zaW9ucyBBKSkKCiAgICAgICAgICAgICAgICAgZm9yIHNxIGluIChzb3J0IHBhdGggIyc8IDprZXkgKGxhbWJkYSAoc3EpIChnZXRmIHNxIDppbmRleCkpKQoKICAgICAgICAgICAgICAgICBmb3IgaW5kZXggZnJvbSAwCiAgICAgICAgICAgICAgICAgd2hlbiAoemVyb3AgKG1vZCBpbmRleCB3aWR0aCkpCiAgICAgICAgICAgICAgICAgICBkbyAoZnJlc2gtbGluZSkKCiAgICAgICAgICAgICAgICAgZG8gKGZvcm1hdCB0ICJ+MkR+QHt+QX59IgogICAgICAgICAgICAgICAgICAgICAgICAgICAgKDErIChnZXRmIHNxIDpudGgpKQogICAgICAgICAgICAgICAgICAgICAgICAgICAgKGVjYXNlIChnZXRmIHNxIDpkaXJlY3Rpb24pCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIChOICNc4oaRKSAoTkUgI1zihpcpIChFICNc4oaSKSAoU0UgI1zihpgpCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIChTICNc4oaTKSAoU1cgI1zihpkpIChXICNc4oaQKSAoTlcgI1zihpYpKSkpKSkK