必ず解ける迷路 in Common Lisp DouKaku?

必ず解ける迷路

以下のルールを満たすn×mの迷路を出力するプログラムを作ってください。

1. 格子状の迷路であること。
2. 経路の幅は均等であること。
3. 迷路のある地点からの全ての地点に到達する経路が1つだけ存在すること。
   ループも認めません。
4. 出力の度にランダムな迷路であること。
   ランダムシードが同じ時に同じ迷路になってしまうのはよいです。

たとえば、n=4, m=5の迷路の出力は以下のようになります。

　｜１｜２｜３｜４｜
―■■■■■■■■■
１■　　　■　　　■
―■■■　■■■　■
２■　　　■　　　■
―■　■■■　■　■
３■　　　　　■　■
―■　■■■　■　■
４■　■　　　■　■
―■　■　■■■　■
５■　■　　　■　■
―■■■■■■■■■

こう言うのは、×の部分が3のルールに違反するのでダメです。
　｜１｜２｜３｜４｜
―■■■■■■■■■
１■　　　■×■　■
―■■■　■■■　■
２■　　　■　　　■
―■　■■■　■　■
３■　　　　　■　■
―■　■■■■■　■
４■　■×××■　■
―■　■×■■■　■
５■　■×××■　■
―■■■■■■■■■

このようなループも2のルールに違反するのでダメです。
　｜１｜２｜３｜４｜
―■■■■■■■■■
１■　　　　　■　■
―■■■　■　■　■
２■　　　■　　　■
―■　■■■　■　■
３■　　　　　■　■
―■　■■■　■　■
４■　■　　　■　■
―■　■　■■■　■
５■　　　　　■　■
―■■■■■■■■■

できたプログラムを使って n=1024, m=1024 の迷路を作るのにかかった時間を教えてください。


難易度高めです。限られたメモリを使って縦方向に無限に広い迷路を
どうやって作るのかを考えると答えが見えてくると思います。
ソースコードはJavaで150行程度になりました。

post comment

Posted feedbacks - Common Lisp

棒倒し法で上から作ると O(n) で済むのでは……って、もう #5296 で指摘されてますね。

出題者さんの用意した方法も想像はついているのですが、それなりに頑張らないと実装できそうにないのでパスしました。

(defun make-maze-1 (upper middle lower &optional arg) ; arg: 最初の行なら真
  (do ((i 1 (+ i 2)))
      ((>= i (length upper)))
    (loop
      (let ((r (random (if arg 4 3))))
        (when (char= #\IDEOGRAPHIC_SPACE
                     (case r
                       (0 (elt middle (1- i)))
                       (1 (elt middle (1+ i)))
                       (2 (elt lower i))
                       (3 (elt upper i))))
          (return (case r
                    (0 (setf (elt middle (1- i)) #\BLACK_SQUARE))
                    (1 (setf (elt middle (1+ i)) #\BLACK_SQUARE))
                    (2 (setf (elt lower i) #\BLACK_SQUARE))
                    (3 (setf (elt upper i) #\BLACK_SQUARE)))))))))

(defun make-maze (m n)
  (let* ((w (+ n n -1))                 ; 迷路の幅
         (whites (make-string w :initial-element #\IDEOGRAPHIC_SPACE))
         (blacks (make-string w :initial-element #\BLACK_SQUARE))
         (alt (let ((s (copy-seq whites)))
                (loop for i from 1 below w by 2 do
                  (setf (elt s i) #\BLACK_SQUARE))
                s))
         (upper (copy-seq whites))
         (middle (copy-seq alt))
         (lower (copy-seq whites))
         (*random-state* (make-random-state t)))
    (format t "■~A■~%" blacks) ; 上の壁
    (make-maze-1 upper middle lower t)
    (format t "■~A■~%■~A■~%" upper middle)
    (dotimes (i (- m 2))
      (replace upper lower)
      (replace middle alt)
      (replace lower whites)
      (make-maze-1 upper middle lower)
      (format t "■~A■~%■~A■~%" upper middle))
    (format t "■~A■~%" lower)
    (format t "■~A■~%" blacks) ; 下の壁
    ))

DouKaku?

必ず解ける迷路

Posted feedbacks - Common Lisp

Index

Feed

Other

Link

Pathtraq