DouKaku?beta

challenge 必ず解ける迷路 

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

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

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

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

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

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

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


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

Posted feedbacks - Flatten

Nested Hidden

たまには一番乗り狙いで。

シンプルに穴掘り法を使いました。 また速度重視ということで手続き型スタイルなScalaになっています。

  • CPU : Athlon64 3000+
  • OS : XP
  • MEM : 1G

な環境で

  • 出力なし: 45～50秒
  • 出力をファイルへリダイレクト : 2分程度

でした。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
import java.util.Random
import java.lang.Integer.parseInt
import scala.collection.mutable.{HashMap, Stack}
import scala.util.Sorting.stableSort

object main{
  def main(args: Array[String]) = {
    mazeGenerate(parseInt(args(0)),parseInt(args(1)))
  }

  type Coord = (int, int)
  final val BLANK = '■'
  final val FILL = '□'

  def mazeGenerate(_n:int, _m:int) = {
    val n = _n*2+1
    val m = _m*2+1
    val map    = new HashMap[Coord, Char]
    val stack  = new Stack[Coord]
    val ramdom = new Random
    val range = Array(0,1,2,3)

    def badCoord_?(c:Coord) = 
        map.getOrElse(c, BLANK) == FILL || c._1 > n-2 || c._1 < 1 || c._2 > m-2 || c._2 < 1
    
    stack += (1,1)
    map(stack.top) = FILL
    var break=false; while(!break) {
      var c = stack.top
      var siblings = Array((c._1, c._2-2), (c._1+2, c._2), (c._1-2, c._2), (c._1, c._2+2))
      if(siblings.forall(badCoord_?(_))){
        stack.pop
        if(stack.isEmpty) { break=true }
      }else {
        var candies = stableSort[int,int](range, { x=>ramdom.nextInt(4) })
        var break2=false;var i= -1; while({i = i+1; !break2&&i<4}) {
          var sibling = siblings(candies(i))
          if(!badCoord_?(sibling)) {
            var (x,y) = (sibling._1-c._1, sibling._2-c._2)
            stack += sibling
            if(x != 0) {
              map((c._1+x/2, c._2)) = FILL
            }else {
              map((c._1, c._2+y/2)) = FILL
            }
            map(sibling) = FILL
            break2 = true
          }
        }
      }
    }

    for(i <- (0 until m); j <- (0 until n)) {
      print(map.getOrElse((j,i), BLANK))
      if(j == n-1){ println("") }
    }
  }
}


効率を度外視して素直に書きました。
全部埋まった状態から掘れるだけ掘って、行き詰まったらバックトラックするだけです。

gosh> (show-maze (maze 4 4))
■■■■■■■■■
■　■　　　■　■
■　■　■　■　■
■　■　■　　　■
■　■　■■■　■
■　　　■　　　■
■■■■■　■■■
■　　　　　　　■
■■■■■■■■■
#<undef>

1024x1024にかかった時間は177秒でした。
(Gauche 0.8.12, Pentium 4 2.0GHz)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
;; -*- coding: euc-jp -*-
(use gauche.array)
(use srfi-27)
(use srfi-42)
(use util.match)
(use gauche.sequence)

(set! (setter array-ref) array-set!) ;; missing in gauche.array
(random-source-randomize! default-random-source)

(define (advance pos d)
  (match-let1 (x . y) pos
    (case d
      [(N) (cons x (- y 1))]
      [(E) (cons (+ x 1) y)]
      [(W) (cons (- x 1) y)]
      [(S) (cons x (+ y 1))])))

(define (inverse d) (case d ((N) 'S) ((S) 'N) ((E) 'W) ((W) 'E)))

(define (maze n m)
  (let1 tab (make-array (shape 0 n 0 m) '())
    (define (diggable? x y)
      (and (<= 0 x (- n 1)) (<= 0 y (- m 1)) (null? (array-ref tab x y))))
    (define (dig pos d)
      (let1 newpos (advance pos d)
        (cond [(diggable? (car newpos) (cdr newpos))
               (push! (array-ref tab (car pos) (cdr pos)) d)
               (push! (array-ref tab (car newpos) (cdr newpos)) (inverse d))
               newpos]
              [else #f])))
    (let rec ((pos '(0 . 0)) (from #f))
      (and pos
           (dolist (d (shuffle '(N E W S)))
             (unless (eq? d from) (rec (dig pos d) (inverse d))))))
    tab))

(define (show-maze tab)
  (dotimes (y (array-ref (array-shape tab) 0 1))
    (dotimes (x (array-ref (array-shape tab) 1 1))
      (display (if (memq 'N (array-ref tab x y)) "■\u3000" "■■")))
    (display "■\n")
    (dotimes (x (array-ref (array-shape tab) 1 1))
      (display (if (memq 'W (array-ref tab x y)) "\u3000\u3000" "■\u3000")))
    (display "■\n"))
  (dotimes (x (array-ref (array-shape tab) 1 1))
    (display "■■"))
  (display "■\n"))

ふつうに配列を使った版。

  • CPU : Athlon64 3000+
  • OS : XP
  • MEM : 1G

な環境で1024 1024が

  • 出力をファイルへリダイレクト : Elapsed Time: 0:00:10.062

でした。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import java.util.Random
import java.lang.Integer.parseInt
import scala.collection.mutable.{HashMap, Stack}
import scala.util.Sorting.stableSort

object main{
  def main(args: Array[String]) = {
    mazeGenerate(parseInt(args(0)),parseInt(args(1)))
  }

  type Coord = (int, int)
  final val BLANK:char = '■'
  final val FILL:char = '□'

  def mazeGenerate(_n:int, _m:int) = {
    val n = _n*2+1
    val m = _m*2+1
    val map:Array[Array[char]] = Array.make(m, 0).map(x=>Array.make(n, BLANK))
    val stack  = new Stack[Coord]
    val ramdom = new Random
    val range = Array(0,1,2,3)

    def badCoord_?(c:Coord) = 
      c._1 > n-2 || c._1 < 1 || c._2 > m-2 || c._2 < 1 || map(c._2)(c._1) == FILL 
    
    stack += (1,1)
    map(1)(1) = FILL
    var break=false; while(!break) {
      var c = stack.top
      var siblings = Array((c._1, c._2-2), (c._1+2, c._2), (c._1-2, c._2), (c._1, c._2+2))
      if(siblings.forall(badCoord_?(_))){
        stack.pop
        if(stack.isEmpty) { break=true }
      }else {
        var candies = stableSort[int,int](range, { x=>ramdom.nextInt(4) })
        var break2=false;var i= -1; while({i = i+1; !break2&&i<4}) {
          var sibling = siblings(candies(i))
          if(!badCoord_?(sibling)) {
            var (x,y) = (sibling._1-c._1, sibling._2-c._2)
            stack += sibling
            map(c._2+y/2)(c._1+x/2) = FILL
            map(sibling._2)(sibling._1) = FILL
            break2 = true
          }
        }
      }
    }

    map.map(_.mkString("")).foreach(println)
  }
}

続いて高速化版です。

1024x1024、出力無しで7秒弱になりました(Pen4 2.0GHz)。約25倍。

- 接続をビットマップで保持
- 方向を整数値で表して条件判断を減らす
- トライすべき方向のリストをshuffleで毎回作るのではなく、すべての可能な組み合わせをあらかじめ計算しといて、ループ内ではそのうち一つをランダムに選ぶ

最後のが一番効きました。shuffleはgeneric functionのディスパッチがあるし、結果のリストのアロケートも行われるのでinner loopで使うと重いのでしょう。 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
;; -*- coding: euc-jp -*-
(use srfi-27)
(use srfi-42)
(use util.combinations)

(random-source-randomize! default-random-source)

(define-constant N -1)
(define-constant S  1)
(define-constant W -2)
(define-constant E  2)

(define (dir->mask d) (ash 1 (+ d 2)))

(define-constant NMASK (dir->mask N))
(define-constant SMASK (dir->mask S))
(define-constant WMASK (dir->mask W))
(define-constant EMASK (dir->mask E))

(define-macro (trials from)
  (define (gen-combs src)
    (list->vector (permutations src)))
  `(vector-ref (case ,from
                 ((,N) ',(gen-combs `(,S ,W ,E)))
                 ((,S) ',(gen-combs `(,N ,W ,E)))
                 ((,W) ',(gen-combs `(,N ,S ,E)))
                 ((,E) ',(gen-combs `(,N ,S ,W))))
               (random-integer 6)))

(define (maze n m)
  (let1 tab (make-vector (* n m) 0)
    (let-syntax [(maze-ref
                  (syntax-rules ()
                    [(_ x y) (vector-ref tab (+ x (* y n)))]))
                 (maze-flag-ior!
                  (syntax-rules ()
                    [(_ x y d)
                     (let1 i (+ x (* y n))
                       (vector-set! tab i (logior (vector-ref tab i)
                                                  (dir->mask d))))]))]
      (define (dig x y d)
        (receive (dx dy) (quotient&remainder d 2)
          (let ((nx (+ x dx)) (ny (+ y dy)))
            (cond [(and (<= 0 nx) (< nx n) (<= 0 ny) (< ny m)
                        (= 0 (maze-ref nx ny)))
                   (maze-flag-ior! x y d)
                   (maze-flag-ior! nx ny (- d))
                   (rec nx ny (- d))]
                  [else #f]))))
      (define (rec x y from)
        (let loop ((ds (trials from)))
          (unless (null? ds)
            (dig x y (car ds))
            (loop (cdr ds)))))
      (rec 0 0 N)
      tab)))

(define (show-maze n m)
  (let1 tab (maze n m)
    (do-ec (: y 0 (* n m) n)
           (begin
             (dotimes (x n)
               (display (if (= 0 (logand NMASK (vector-ref tab (+ x y))))
                          "■■" "■\u3000")))
             (display "■\n")
             (dotimes (x n)
               (display (if (= 0 (logand WMASK (vector-ref tab (+ x y))))
                          "■\u3000" "\u3000\u3000")))
             (display "■\n")))
    (dotimes (x n) (display "■■"))
    (display "■\n")))


これは、ありですか？
一応、毎回ランダムに結果は変わるのですが。
実行結果：
 $ gosh 123.scm
xxxxxxxxxxx
x         x
x xxxxxxx x
x       x x
x xxxxxxx x
x       x x
x xxxxxxx x
x       x x
x xxxxxxx x
x       x x
xxxxxxxxxxx
 $ gosh 123.scm
xxxxxxxxxxx
x       x x
x xxxxxxx x
x       x x
x xxxxxxx x
x         x
x xxxxxxx x
x       x x
x xxxxxxx x
x       x x
xxxxxxxxxxx
 $ gosh 123.scm
xxxxxxxxxxx
x         x
x xxxxxxx x
x       x x
x xxxxxxx x
x       x x
x xxxxxxx x
x       x x
x xxxxxxx x
x       x x
xxxxxxxxxxx
 $

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
(use srfi-27)

(define (showmaze n m)
  (let1 x (random-integer m)
    (dotimes (i m)
      (display (if (= i 0) "xx" "x "))
      (dotimes (j (- n 2)) (display "xx"))
      (display (if (= i 0) "xxx\n" "x x\n"))
      (display "x ")(dotimes (j (- n 2)) (display "  "))
      (display (if (= i x) "  x\n" "x x\n")))
    (dotimes (j m) (display "xx")) (display "x\n")))

(define (main args)
  (random-source-randomize! default-random-source)
  (showmaze 5 5))


解いても楽しくない迷路になりそうですが、ルールは満たしていますね。
あと、めっちゃ速そう(笑)

棒倒し法で実装しました. 
1024 x 1024の迷路生成に約48秒 (CPU: Intel P4 Northwood 2.8 GHz) かかりました. 
mapメソッドとgen_wallメソッドの処理の1行目のコメントは, 各メソッドの1行バージョンです. 
全体をone-lineにする方法が見つからなかったのでせめてもの抵抗ということで.

see: アルゴリズム講座:棒倒し法 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
require 'matrix'
N, M = 5, 4
class Maze
  MARK, SPC = '*', ' '
  def initialize(n, m) #基準点を生成し, その上と左の壁の有無と真理値が対応. 
    @map = Matrix[*Array.new(@n = n){Array.new(@m = m)}].map{Array.new(2)}
    gen_maze
  end
  def map #得たマップデータを対応する記号で表現
    #Array.new(2*@n-1){|i| Array.new(2*@m-1){|j| i%2 == j%2 ? (i%2 == 1 ? MARK : SPC) : (@map[i.div(2), j.div(2)][i%2] ? MARK : SPC)}.unshift(MARK).push("#{MARK}\n")}.unshift(str = "#{MARK*(2*@m+1)}\n").push(str).join
    print "#{MARK*(2*@m+1)}\n"
    (2*@n-1).times{|i|
      print MARK
      (2*@m-1).times{|j|
        if i%2 == j%2
          print i%2 == 1 ? MARK : SPC
        else
          print @map[i.div(2), j.div(2)][i%2] ? MARK : SPC
        end
      }
      print "#{MARK}\n"
    }
    print "#{MARK*(2*@m+1)}\n"
  end
  def gen_maze #左端の列だけ4種の壁がランダムで生成. 他は3種のみ. 
    (@m-1).times{|j| (@n-1).times{|i| gen_wall(i, j, (j == 0 ? 4 : 3))}}
  end
  def gen_wall(i, j, n) #ランダムに壁を生成. もし壁がすでにあれば再帰. 
    #@map[x = i+((r=rand(n))==1 ? 1 : 0), y = j+(r==2 ? 1 : 0)][r%2] ? gen_wall(i, j, n) : @map[x, y][r%2] = true
    case rand(n)
    when 0: x, y, k = i,   j, 0 #上
    when 1: x, y, k = i+1, j, 0 #下
    when 2: x, y, k = i, j+1, 1 #右
    when 3: x, y, k = i,   j, 1 #左
    end
    @map[x, y][k] ? gen_wall(i, j, n) : @map[x, y][k] = true
  end
  private :gen_maze, :gen_wall
end
maze = Maze.new(N, M)
maze.gen_maze
maze.map

はじめまして、通りすがりです。

懐かしいお題だったので、勢いで作ってみました。一応、テストはしましたけど、まだバグってるかも知れません。

開発環境は、
・東芝のノート：AX/530LL＋Mem512（=７０４位）・VC＋＋２００８　Express（C++＆STL）・6時間くらいの時間。

実行環境。
・上記の機材。・速度向け最適化。・リリースビルド。
＝＞ファイルにリダイレクトで3秒位でした。迷路の生成自体は1秒ちょいってとこじゃないでしょうか。
えぇーっと、ライブラリが良いのと、ネーティブコードなのでアドバンテージとれてるかもしれないです。

注意ですけど、最初にがーっとメモリ取るので環境によってはあんまり好ましくない動作をするかもしれません。ウチでは大丈夫というのはあてになりませんので。。。

長くなりましたけど、面白かったです。 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <time.h>
#include <stdexcept>
class Maze_t{
    typedef unsigned short MazeElement;
    typedef std::vector<MazeElement> maze_t;
    int Width_,Height_;
    maze_t Data;
    struct Point2{
        int x,y;
        void ToZero(){x=y=0;}
        void Set(int x_, int y_){x=x_; y=y_;}
    };
    
public:
    enum Flags{
        Left=0,
        Up,
        Right,
        Down,
        Visit,
    };
    Maze_t(size_t W,size_t H){
        Create(W,H);
    }
    void Create(size_t W,size_t H){
        Destroy();
        Width_=W;Height_=H;
        Data.resize(W*H);
        std::fill(Data.begin(),Data.end(),int(0));
        Generate();
    }
    void Destroy(){
        Data.clear();
        Width_ = 0;Height_= 0;
    }
    int Width(){ return Width_;}
    int Height(){ return Height_;}
    MazeElement WallInfo(int x, int y){
        if(!CanVisit(x,y)) return 0; 
        return GetElement(x,y);
    }
protected:
    bool CanVisit(int x, int y){
        if(x<0) return false;
        if(y<0) return false;
        if(Width()<=x) return false;
        if(Height()<=y) return false;
        return true;
    }
    bool AlreadyVisit(int x,int y){
        if(!CanVisit(x,y)) return true;
        return GetElement(x,y)>>Visit & 1;
    }
    void MarkVisit(int x,int y){
        if(CanVisit(x,y) == false) return;
        MazeElement& Me = GetElement(x,y);
        Me = Me | 1 << Visit;
    }
    MazeElement& GetElement(int x,int y){
        return Data[Width()*y+x];
    }
    void EraseWall(Point2 Base,Point2 To,int command){
        char Flg1[] = {Left,Up,Right,Down};
        char Flg2[] = {Right,Down,Left,Up};
        MazeElement* p;
        p = &(GetElement(Base.x,Base.y));
        (*p) = (*p) | (1<<Flg1[command]);
        p = &(GetElement(Base.x+To.x,Base.y+To.y));
        (*p) = (*p) | (1<<Flg2[command]);
    }
    struct Uni{
        union{
            int Int;
            char Char[4];
        };
    };
    void Generate(){//メモリ等確保後に実行しないと不整合起こします。つまり単体で使用しないでください。Create関数がエントリです。
        Point2 V[]={{-1,0},{0,1},{1,0},{0,-1}};
        Point2 T={rand()%Width(),rand()%Height()};
        std::vector<Point2> pov;
        std::vector<int> command;
        std::vector<int> rotate;
        Uni U;
        U.Int = 0x03020100;
        std::random_shuffle(U.Char,U.Char+4);
        int i=0;
        pov.push_back(T);
        command.push_back(i);
        rotate.push_back(U.Int);
        MarkVisit(T.x,T.y);
        while(pov.size() != 0){
            T = pov.back();
            i = command.back();
            U.Int = rotate.back();
            for(;i<4;i++){
                if(CanVisit(T.x+V[ U.Char[i]].x,T.y+V[ U.Char[i]].y)){
                    if(AlreadyVisit(T.x+V[ U.Char[i]].x,T.y+V[ U.Char[i]].y)) continue;
                    MarkVisit(T.x+V[ U.Char[i]].x,T.y+V[ U.Char[i]].y);
                    EraseWall(T,V[ U.Char[i]], U.Char[i]);
                    T.x=T.x+V[ U.Char[i]].x;
                    T.y=T.y+V[ U.Char[i]].y;
                    pov.push_back(T);
                    command.push_back(i);
                    rotate.push_back(U.Int);
                    i=0;
                    std::random_shuffle(U.Char,U.Char+4);
                }
            }
            pov.pop_back();
            command.pop_back();
            rotate.pop_back();
        }
    }
};
void PrintMaze(Maze_t& M){
    char W='W',R=' ';
    for(int i=0;i<M.Height();i++){
        for(int k=0;k<3;k++){
            for(int j=0;j<M.Width();j++){
                int wall = M.WallInfo(j,i);
                if(k==0) printf("%c%c%c",W, ((wall>>M.Down)&1)? R:W, W);
                if(k==1) printf("%c%c%c",((wall>>M.Left)&1)? R:W, ((wall>>M.Visit)&1)? R:W, ((wall>>M.Right)&1)? R:W);
                if(k==2) printf("%c%c%c",W, ((wall>>M.Up)&1)? R:W, W);            
            }
            puts("");
        }
    }
}
void PrintMaze2(Maze_t& M){
    char *W="■",*R="　";
    for(int j=0;j<M.Width();j++) printf("%s%s",W,W);
    puts(W);
    for(int i=0;i<M.Height();i++){
        for(int k=1;k<3;k++){
            printf("%s",W);
            for(int j=0;j<M.Width();j++){
                int wall = M.WallInfo(j,i);
                if(k==0) printf("%s%s", ((wall>>M.Down)&1)? R:W, W);
                if(k==1) printf("%s%s", ((wall>>M.Visit)&1)? R:W, ((wall>>M.Right)&1)? R:W);
                if(k==2) printf("%s%s", ((wall>>M.Up)&1)? R:W, W);            
            }
            puts("");
        }
    }
}
int main(){
    //srand(100);
    srand(time(NULL));
    Maze_t m(12,6);
    //Maze_t m(1024,1024);
    PrintMaze2(m);
    return 0;
}

壁に孔をあける位置をランダムに。マシンが遅いので、Pentium2 266MHz で psyco を使って4分くらいです。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# coding: shift_jis

import codecs
import random

def create_maze(path, n, m):
    io = codecs.open(path, "w", "shift_jis")
    holes = [random.randint(1, 2 * m - 1) for _ in xrange(n - 1)]
    for y in xrange(2 * m + 1):
        for x in xrange(2 * n + 1):
            if x == 0 or x == 2 * n or y == 0 or y == 2 * m:
                io.write(u"■")
            elif x % 2 == 1 or holes[x // 2 - 1] == y:
                io.write(u"　")
            else:
                io.write(u"■")
        io.write("\n")

def main():
    create_maze("a.txt", 1024, 1024)

if __name__ == "__main__":
    try:
        import psyco
    except ImportError:
        pass
    else:
        psyco.full()
    main()

これもまた#5282と同じように、解いても面白くなさそうな迷路が出力されますね。そしてすっごい速そうです。

さらに、メモリ効率がすごくよいですね。 実はこのアルゴリズムと同じメモリ効率(nに比例)で、しかも解いても面白い迷路が出力できるアルゴリズムが存在します。


速さには自信があります。(笑)
>限られたメモリを使って縦方向に無限に広い迷路を
>どうやって作るのかを考えると答えが見えてくると思います。
をすっごくまじめに考えて、最小のメモリで無限の迷路を作り出すことばかり考えていたら、
こんなふざけたアイデアしか思いつかなかったので。
すみません。

穴掘り法ですね。 迷路生成1秒ですか。さすがC++は速いなぁ。


メモリ使用量はO(1)なので確かに理想的ですね。速さも文句なしです。でも、さすがにそこまでのメモリ効率は想定していませんでした(笑)

他のコメントにも書きましたが、O(n)のアルゴリズムがあるんですよ。解いて楽しい迷路生成のメモリ効率としてはそれ以上のアルゴリズムは無いと踏んでます。 時間のあるときにでも考えてみてください。


棒倒し法で何も工夫していない上に、なでしこなので速度は遅め・・・。
6分57秒でした。表示に30秒くらいかかってる気がします。
(CPU:Athlon X2 3600+ [1.9GHz*2] RAM:2GB) 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
!変数宣言が必要

#幅/高さ
Xとは整数=1024
Yとは整数=1024

迷路とは配列
Iとは整数
Jとは整数
ワクとは文字列
結果とは文字列
X=X*2-1
Y=Y*2-1

#奇数のマスに置く
Iで0からX-1まで繰り返す
    Jで0からY-1まで繰り返す
        もし(I%2=1&&J%2=1)ならば
            迷路[J,I]="■"
        違えば
            迷路[J,I]="　"

#一番左の列について
Iで0からY-1まで繰り返す
    もし(I%2=1)ならば
        壁生成(迷路,I,1,4)

#そのほかの列について
もし(X>3)ならば
    Iで3からX-1まで繰り返す
        Jで0からY-1まで繰り返す
            もし(I%2=1&&J%2=1)ならば
                壁生成(迷路,J,I,3)

#整形して表示
ワク="■"をX+2だけリフレイン
結果=ワク&改行
(TOSTR(迷路)の","を""に置換)を反復
    結果=結果&"■"&対象&"■{~}"
結果=結果&ワク
結果を表示

●壁生成(MAP,X,Y,RND)
    Mとは整数
    Nとは整数
    乱数初期化
    乱数(RND)で条件分岐
        0ならば,M=X-1;N=Y #上
        1ならば,M=X;N=Y+1 #右
        2ならば,M=X+1;N=Y #下
        3ならば,M=X;N=Y-1 #左
    もし(MAP[M,N]<>"■")ならば
        MAP[M,N]="■"
    違えば
        壁生成(MAP,X,Y,RND)


メモリを O(n) でしか使わないのを書いてみました。
最後の行で辻褄を合わせていますが、それなりな迷路になっているかと思います。

n=4, m=5, seed=6 でこんな感じになりました。

■■■■■■■■■
■　■　　　■　■
■　■　■■■　■
■　■　　　　　■
■　■　■■■■■
■　　　■　■　■
■■■　■　■　■
■　　　　　■　■
■■■■■　■　■
■　　　　　　　■
■■■■■■■■■

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Iterator;
import java.util.Random;


public class Sample123 {
    public static void main(String[] args) {
        try {
            BufferedWriter writer = new BufferedWriter(new FileWriter("result.txt"));

            long start = System.currentTimeMillis();
            Iterator<String> ite = new MazeLineIterator(4, 5, 6);
            while (ite.hasNext()) {
                writer.append(ite.next());
                writer.newLine();
            }
            long end = System.currentTimeMillis();

            writer.close();
            System.out.println("elapse: " + (end - start) + "(ms)");
        } catch (IOException ex) {
            ex.printStackTrace();
        }
    }
}

class MazeLineIterator implements Iterator<String> {
    public static final String WALL_CHAR = "■";
    public static final String SPACE_CHAR = "　";

    private static final int WALL_AREA = 0;

    private final Random random_;

    private long line_ = -1;
    private boolean oddLine_ = false;    // oddLine_ == true の時が通路の行、falseの時が柱の行
    private int counter_ = 1;

    private final int maxCol_;
    private final long maxRow_;
    private final int[] mazeLine_;

    public MazeLineIterator(int col, long row) {
        maxCol_ = col;
        maxRow_ = row;
        mazeLine_ = new int[col * 2 + 1];
        random_ = new Random();
    }
    public MazeLineIterator(int col, long row, long seed) {
        maxCol_ = col;