必ず解ける迷路 DouKaku?

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

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

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

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

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

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

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


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

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

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

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

な環境で

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

でした。

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)

;; -*- 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

でした。

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で使うと重いのでしょう。

;; -*- 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
 $

(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: アルゴリズム講座:棒倒し法

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秒ちょいってとこじゃないでしょうか。
えぇーっと、ライブラリが良いのと、ネーティブコードなのでアドバンテージとれてるかもしれないです。

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

長くなりましたけど、面白かったです。

#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分くらいです。

# 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)

!変数宣言が必要

#幅/高さ
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 でこんな感じになりました。

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

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;
        maxRow_ = row;
        mazeLine_ = new int[col * 2 + 1];
        random_ = new Random(seed);
    }


    public boolean hasNext() {
        return (line_ < maxRow_);
    }

    public String next() {
        if (line_ < 0 || (line_ == maxRow_ - 1 && !oddLine_)) {
            for (int index = 0; index < mazeLine_.length; index++) {
                mazeLine_[index] = WALL_AREA;
            }
        } else {
            if (oddLine_) {
                createOddLine();
            } else {
                createEvenLine();
            }
        }

        if (!oddLine_) line_++;
        oddLine_ = !oddLine_;
        return createDisplay(mazeLine_);
    }

    private String createDisplay(int[] line) {
        StringBuilder builder = new StringBuilder(line.length);
        for (int index: line) {
            //builder.append(index);
            builder.append(isWall(index)? WALL_CHAR: SPACE_CHAR);
        }
        return builder.toString();
    }


    private void createOddLine() {
        int area = 0;
        for (int index = 0; index < maxCol_; index++) {
            int lastArea = mazeLine_[index * 2 + 1];
            if (isWall(lastArea)) {
                if (isWall(area)) {
                    area = counter_++;
                }
                mazeLine_[index * 2 + 1] = area;
            } else {
                if (!isWall(area)) {
                    if (area == lastArea) {
                        mazeLine_[index * 2] = WALL_AREA;
                    } else {
                        area = replaceArea(area, lastArea);
                    }
                } else {
                    area = lastArea;
                }
            }

            if (index > 0 && line_ == maxRow_ - 1) {
                if (mazeLine_[index * 2 + 1] != mazeLine_[index * 2 - 1]) {
                    area = replaceArea(mazeLine_[index * 2 - 1], mazeLine_[index * 2 + 1]);
                    mazeLine_[index * 2] = area;
                }
            }
            if (index == maxCol_ - 1) break;
            if (random_.nextBoolean()) {
                area = WALL_AREA;
            }
            mazeLine_[(index + 1) * 2] = area;
        }
    }

    private void createEvenLine() {
        for (int index = 0; index < maxCol_; index++) {
            int lastArea = mazeLine_[index * 2 + 1];
            if (searchArea(lastArea, index * 2 + 1) && random_.nextBoolean()) {
                mazeLine_[index * 2 + 1] = WALL_AREA;
            }
            mazeLine_[(index + 1) * 2] = WALL_AREA;
        }
    }

    private boolean isWall(int area) {
        return (area == WALL_AREA);
    }
    private int replaceArea(int oldArea, int newArea) {
        if (oldArea < newArea) {
            return replaceArea(newArea, oldArea);
        }
        for (int index = 0; index < mazeLine_.length; index++) {
            if (mazeLine_[index] == oldArea) {
                mazeLine_[index] = newArea;
            }
        }
        if (oldArea == counter_) {
            counter_--;
        }
        return newArea;
    }

    private boolean searchArea(int area, int excludeIndex) {
        for (int index = 0; index < mazeLine_.length; index++) {
            if (index == excludeIndex) continue;
            if (mazeLine_[index] == area) return true;
        }
        return false;
    }

    public void remove() {
        throw new UnsupportedOperationException();
    }
}

「1024 x 1024」くらいならメモリ使用量が問題になることはないのかなと、あまり考えずに普通に書きました。

「1024 x 1024」で6秒くらい。CPUスペックは、AMD Athlon 64 X2の2GHzだったと思います。

アルゴリズムは、迷路の盤面を配列で用意して、１箇所から始めてランダムに少しずつ迷路を広げていく方法を取っています。

「10 x 10」のサンプル出力は次の通りです。

#####################
#     # #       #   #
# ### # # ####### ###
# #         #       #
# # # # # ### ### ###
# # # # #       # # #
# ### ##### # # ### #
# # #     # # #   # #
### # ### # ### ### #
#       # # #       #
# ### ######### ### #
# #           # # # #
### ### # ##### # ###
#     # #     #     #
# ##### # ####### ###
# #     #       # # #
####### # # # # ### #
#   #   # # # # # # #
# ##### ### # ### # #
#         # #       #
#####################

see: AltEnvライブラリを使っています

module Main

import Bool, Int, String, StringCast, Array
import System, Misc, StdIO, OptRandom, MersenneTwister, Trace

:: MazeCell = Cell !Bool !Bool //right, bottom

Start w
  # (t,w) = tickCount w
    (f,w) = stdio w
    (_,f) = writeLine 0 f
    (_,f) = writeMaze (maze n m (genRandInt t)) f
    (_,w) = close f w
  = w
  where
  cmd = getCommandLine
  n = toInt cmd.[1]
  m = toInt cmd.[2]
  get maze row col = maze.[row * n + col]

  writeMaze maze f = writeMaze maze 0 f
    where
    writeMaze maze row f
      | row == m = (PassV, f)
      = f |> write "#"
          $> printRoom 0
          $> write "\r\n#"
          $> printWall 0
          $> write "\r\n"
          $> writeMaze maze (row + 1)
      where
      m = size maze / n
      printWall col f
        | col == n = (PassV, f)
        = case get maze row col of
            Cell _ False = f |> write "##" $> printWall (col + 1)
            _            = f |> write " #" $> printWall (col + 1)

      printRoom col f
        | col == n = (PassV, f)
        = case get maze row col of
            Cell False _ = f |> write " #" $> printRoom (col + 1)
            _            = f |> write "  " $> printRoom (col + 1)

  writeLine col f
    | col == n = f |> write "#\r\n"
    = f |> write "##" $> writeLine (col + 1)

::*CellPool = CellPool !*{!(!Int,!Int)} !Int
isEmptyPool c=:(CellPool _ 0) = (True, c)
isEmptyPool c = (False, c)
getNextCell (CellPool ls sz) [r:rand]
    | sz == 1
      # (e1,ls) = ls![0]
      = (e1, CellPool ls 0, rand)
    # i = (abs r) rem sz
      (e1,ls) = ls![i]
      (e2,ls) = ls![sz-1]
      ls = {ls & [i] = e2}
    = (e1, CellPool ls (sz - 1), rand)
addCell x y (CellPool ls sz)
    # ls = {ls & [sz] = (x,y)}
    = CellPool ls (sz + 1)

maze n m rand =
    let
      sz = n * m
      marks = asUnboxedArray $ createArray sz False
      cells = asStrictArray $ createArray sz (Cell False False)
      pool = addCell 0 0 (CellPool (createArray sz (0,0)) 0)
    in
      expand marks cells pool rand
  where
    get x y arr = arr![x*n+y]
    put e x y arr = {arr & [x*n+y] = e}

    expand marks cells pool rand
      # (b,pool) = isEmptyPool pool
      | b = cells
      # ((x,y), pool, rand) = getNextCell pool rand
        (cand, marks) = filterCells marks [(x-1,y),(x,y-1),(x+1,y),(x,y+1)]
        (sel, rest, rand) = selectCells cand rand
      #! cells = updateCells x y sel cells
         marks = foldl (\marks (x,y) = put True x y marks) marks sel
         pool = foldl (\pool (x,y) = addCell x y pool) pool sel
      = case rest of
          [] = expand marks cells pool rand
          _  # pool = addCell x y pool
             = expand marks cells pool rand

    filterCells marks ls = f [] marks ls where
      f ls marks [] = (ls, marks)
      f ls marks [(x,y):ee]
        | x < 0 || y < 0 || x >= m || y >= n = f ls marks ee
        # (k,marks) = get x y marks
        | k = f ls marks ee
            = f [(x,y):ls] marks ee

    selectCells ls [r:rand] = let (e1,e2) = f ls 1 [] [] in (e1, e2, rand) where
      f [] _ e1 e2 = (e1, e2)
      f [e:ee] t e1 e2
        | r bitand t == 0 = f ee (t << 1) e1 [e:e2]
                          = f ee (t << 1) [e:e1] e2

    updateCells x y ls cells = f ls cells where
      f :: ![(Int,Int)] !*{!MazeCell} -> *{!MazeCell}
      f [] cells = cells
      f [(x1,y1):ls] cells
        # (c0, cells) = get x y cells
          (c1, cells) = get x1 y1 cells
        | x1 < x = let (Cell r b) = c1 in put (Cell r True) x1 y1 cells |> f ls
        | y1 < y = let (Cell r b) = c1 in put (Cell True b) x1 y1 cells |> f ls
        | x1 > x = let (Cell r b) = c0 in put (Cell r True) x y cells |> f ls
        | y1 > y = let (Cell r b) = c0 in put (Cell True b) x y cells |> f ls

O(n)のアルゴリズムは、棒倒し法しか思いつかない。
穴掘り法はある程度、美しいんだけど、O(n^2)だし。

棒倒し法で棒を倒す方向を決定するのに、
周囲の環境を見て決めるように、パラメータチューニングするしかないのかなぁ。
と考え中。

↓は綺麗だけどお題を満たさない答え。　迷路(笑)

#include<stdio.h>
#include<stdlib.h>

int main()
{
    int x,y,n,m;
    n = 10;
    m = 20;

    for (y = 0; y < m; y++){
        for (x = 0; x < n; x++){
            printf(rand() > RAND_MAX / 2 ? "／" : "＼");        
        }
        printf("\n");
    }
}

棒倒し法で上から作ると 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) ; 下の壁
    ))

所要時間は Celeron 2.66GHz, CLISP で 2.84 秒でした。

1024x1024を出力したら、Pen4 2.4GHzで 10秒弱でした。

棒倒し法も空間計算量がO(n)なんですね。 O(nm)と勘違いしてました・・orz

ルールは満たしてませんが、見栄えのする迷路が出てきますね。

棒倒し法も空間計算量がO(n)ですね。
すみません勘違いしてました。

私の考えたアルゴリズムと同じです。
棒倒し法の1行バッファ版と言えるようです。

以下、n=5, m=5の迷路の例でアルゴリズムを解説します。

・最初の行
Ｓ■■■■■■■■■■■←
まずバッファを用意して、全て壁にします。

・1行目(奇数行)
Ｓ■■■■■■■■■■■
１■★■★■★■★■★■←
★の箇所に穴を開けます。

Ｓ■■■■■■■■■■■
１■Ａ■Ｂ■Ｃ■Ｄ■Ｅ■←
穴を開けた場所をＡ～Ｅとします。

Ｓ■■■■■■■■■■■
１■Ａ★Ｂ★Ｃ★Ｄ★Ｅ■←
★の箇所に穴を開けるかどうかを乱数で決定します。

Ｓ■■■■■■■■■■■
１■Ａ▲Ｂ★Ｃ★Ｄ★Ｅ■←
たとえば▲に穴を開ける場合。

Ｓ■■■■■■■■■■■
１■ＡＡＡ★Ｃ★Ｄ★Ｅ■←
ＡとＢの領域が結合されるため、Ｂ領域をＡ領域に統合します。
仮にＢ領域に飛び地があっても、それもＡ領域に統合します。
また、★の左右が同じ領域だった場合は、穴を開けてはいけません。
ループ経路が出来てしまうからです。

Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■←
この調子で穴を開けていきます。
全ての★を乱数で決定したら1行確定です。

・2行目(偶数行)
Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■Ａ☆Ａ☆Ａ☆Ａ★Ｅ■←
☆の箇所を壁にします。

Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■Ａ■Ａ■Ａ■Ａ■Ｅ■←
★の箇所はすでに壁なので特に何もしません。

Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■☆■☆■☆■☆■Ｅ■←
☆の箇所を壁にするかどうかを乱数で決定します。

ただし、残り１つになっているＥの列は壁になってはいけません。
また、４つの☆は３つまでは壁にしてもよいですが、
最後のひとつは壁にしてしてはいけません。
４つとも壁にしてしまうと
　Ｓ■■■■■■■■■■■
　１■ＡＡＡＡＡＡＡ■Ｅ■
　２■■■■■■■■■Ｅ■←
こうなって、Ａの領域に侵入できなくなってしまうからです。

Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■Ａ■■■Ａ■■■Ｅ■←
乱数を使って結局２箇所を壁にすることになりました。
全ての☆を乱数で決定したら1行確定です。

・3行目(奇数行)
Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■Ａ■■■Ａ■■■Ｅ■
３■Ａ■★■Ａ■★■Ｅ■←
1行目と同じく、★の箇所に穴を開けてＢ,Ｃ領域と
します。

Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■Ａ■■■Ａ■■■Ｅ■
３■Ａ★Ｂ★Ａ★Ｃ★Ｅ■←
★の箇所に穴を開けるかどうかを乱数で決定します。


あとは同じように、
偶数行→奇数行→偶数行→・・・
と繰り返します。


・9行目(最後の一つ前の行&奇数行)
Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■Ａ■■■Ａ■■■Ｅ■
３■ＡＡＡ■Ａ■ＣＣＣ■
４■■■Ａ■■■■■Ｃ■
５■Ｂ■Ａ■ＤＤＤ■Ｃ■
６■Ｂ■Ａ■Ｄ■Ｄ■Ｃ■
７■ＡＡＡ■Ｃ■ＣＣＣ■
８■Ａ■Ａ■Ｃ■Ｃ■Ｃ■
９■Ａ■Ａ■Ｃ■Ｃ■Ｃ■←
最後の一つ前の行は辻褄あわせが必要です。
具体的には、すべての領域を統合しなければなりません。

Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■Ａ■■■Ａ■■■Ｅ■
３■ＡＡＡ■Ａ■ＣＣＣ■
４■■■Ａ■■■■■Ｃ■
５■Ｂ■Ａ■ＤＤＤ■Ｃ■
６■Ｂ■Ａ■Ｄ■Ｄ■Ｃ■
７■ＡＡＡ■Ｃ■ＣＣＣ■
８■Ａ■Ａ■Ｃ■Ｃ■Ｃ■
９■Ａ■Ａ★Ｃ■Ｃ■Ｃ■←
今回は、たまたまＡ領域とＣ領域しかないため、
★の箇所の壁を取り除けばＯＫです。

Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■Ａ■■■Ａ■■■Ｅ■
３■ＡＡＡ■Ａ■ＣＣＣ■
４■■■Ａ■■■■■Ｃ■
５■Ｂ■Ａ■ＤＤＤ■Ｃ■
６■Ｂ■Ａ■Ｄ■Ｄ■Ｃ■
７■ＡＡＡ■Ｃ■ＣＣＣ■
８■Ａ■Ａ■Ｃ■Ｃ■Ｃ■
９■Ａ★Ａ☆Ｃ★Ｃ★Ｃ■
★☆の箇所に穴を開けるか乱数で決定します。

Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■Ａ■■■Ａ■■■Ｅ■
３■ＡＡＡ■Ａ■ＣＣＣ■
４■■■Ａ■■■■■Ｃ■
５■Ｂ■Ａ■ＤＤＤ■Ｃ■
６■Ｂ■Ａ■Ｄ■Ｄ■Ｃ■
７■ＡＡＡ■Ｃ■ＣＣＣ■
８■Ａ■Ａ■Ｃ■Ｃ■Ｃ■
９■Ａ■ＡＡＡ★Ａ★Ａ■
☆確定まで。
この例では、☆以外はたまたま左右が同じ領域なので、
選択肢がありません。

Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■Ａ■■■Ａ■■■Ｅ■
３■ＡＡＡ■Ａ■ＣＣＣ■
４■■■Ａ■■■■■Ｃ■
５■Ｂ■Ａ■ＤＤＤ■Ｃ■
６■Ｂ■Ａ■Ｄ■Ｄ■Ｃ■
７■ＡＡＡ■Ｃ■ＣＣＣ■
８■Ａ■Ａ■Ｃ■Ｃ■Ｃ■
９■Ａ■ＡＡＡ■Ａ■Ａ■
Ａ領域とＣ領域が統合されたため、
残りの★も穴をあけられなくなりました。

・最後の行
Ｓ■■■■■■■■■■■
１■ＡＡＡＡＡＡＡ■Ｅ■
２■Ａ■■■Ａ■■■Ｅ■
３■ＡＡＡ■Ａ■ＣＣＣ■
４■■■Ａ■■■■■Ｃ■
５■Ｂ■Ａ■ＤＤＤ■Ｃ■
６■Ｂ■Ａ■Ｄ■Ｄ■Ｃ■
７■ＡＡＡ■Ｃ■ＣＣＣ■
８■Ａ■Ａ■Ｃ■Ｃ■Ｃ■
９■Ａ■ＡＡＡ■Ａ■Ａ■
Ｅ■■■■■■■■■■■
全て壁で埋めます。

これでおしまいです。


私の書いたJavaコードだと出力無しで1372ミリ秒でした。
　　PentiumM 2.1GHz
　　java version "1.6.0_02"
　　Java(TM) SE Runtime Environment (build 1.6.0_02-b05)
　　Java HotSpot(TM) Server VM (build 1.6.0_02-b05, mixed mode)

棒倒し法、たしかにO(n)ですね。

ご想像のとおり、私の意図したアルゴリズムは実装がちょっと面倒です。

反則だろうと思って投稿を思い止まっていたのにーｗ

棒を倒す方向を右か下に限定することによって
速度もコード量もそれなりではないかと思います☆

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define X 17
#define Y 15
int main(void){
  char maze[X - 1], *pattern[] = {"  ", "■"};
  int i, j;
  srand((unsigned)time(NULL));
  for(i = 0; i < X; i++)
    printf("■■");
  printf("■\n■%*s", X * 4 - 2, "");
  for(j = 0; j < Y - 1; j++){
    printf("■\n■  ");
    for(i = 0; i < X - 1; i++)
      printf("■%s", pattern[maze[i] = rand() / (RAND_MAX + 1.0) * 2]);
    printf("■\n■  ");
    for(i = 0; i < X - 1; i++)
      printf("%s  ", pattern[1 - maze[i]]);
  }
  printf("■\n■");
  for(i = 0; i < X; i++)
    printf("■■");
  printf("\n");
  return 0;
}

迷路がお題を満たす(全ての場所にいける&ループ無し) ための必要十分条件は
「全ての基点(マップ上で(i, j)=(偶数, 偶数)の点) が外壁と一ヶ所でだけ繋がっている」
なんじゃないかなぁと思って、
お題を満たすような迷路を全て生成し得るような方法を考えてみました。

領域量はO(mn)要ります。1024*1024で2分ぐらい。


ちなみに棒倒し法なんかだと、例えば次のようなものを生成できません。

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

class Maze
  def initialize(m, n)
    @rows = m
    @cols = n
    @field = Array.new(2*@rows+1) do |i|
      (i % 2 == 0) ? ('# ' * @cols + '#') : ('#' + ' ' * (2*@cols-1) + '#')
    end
    @field[0] = @field[-1] = '#' * (2*@cols+1)
  end

  def gen
    # number of connections to the wall
    bases = Array.new(@rows+1) do |i|
      if i == 0 || i == @rows
        Array.new(@cols+1, 1)
      else
        Array.new(@cols+1) {|j| (j == 0 || j == @cols) ? 1 : 0 }
      end
    end
    uc = []  # candidates of next selection
    (1 .. @rows-1).each {|i| uc << [i, 1] << [i, @cols-1] }
    (2 .. @cols-2).each {|j| uc << [1, j] << [@rows-1, j] }

    until uc.empty?
      y, x = uc.slice!(rand(uc.size))
      next if bases[y][x] > 0
      dirs = [[+1, 0], [-1, 0], [0, +1], [0, -1]].sort_by { rand }
      dirs.each do |mv|
        y_, x_ = y + mv[0], x + mv[1]
        if bases[y_][x_] == 1
          @field[2*y+mv[0]][2*x+mv[1]] = ?#
          bases[y][x] += 1
          break
        end
      end
      dirs.each do |mv|
        y_ , x_ = y + mv[0], x + mv[1]
        uc << [y_, x_] if bases[y_][x_] == 0
      end
    end
    self
  end

  def p
    @field.each {|row| puts row }
  end
end


M, N = 10, 10
maze = Maze.new(M, N)
#maze.p
maze.gen.p

棒倒し法を用いています。
1024x1024 迷路構築のみで平均18秒弱。
(CPU : 1.4GHz, RAM : 256MB)

ex)
echo '<pre>'.Maze(5, 5).'</pre>';

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

see: 自動生成迷路

<?php
function Maze($x, $y)
{
    /* init     */
    $l_array = str_repeat('1', $x*2-1+2);
    $s_array = array_fill(0, $x*2-1, '0');
    $p_array = str_split(str_repeat('01', $x-1).'0');
    $work = array();
    $work[] = $s_array;
    $work[] = $p_array;
    $work[] = $s_array;

    /* build    */
    $maze = $l_array."\n";
    for ($row = 0; $row < $y-1; $row++) {
        for ($col = 0; $col < $x-1; $col++) {
            wall($work, $row, $col);
        }
        $maze .= '1'.implode('', array_shift($work))."1\n";
        $maze .= '1'.implode('', array_shift($work))."1\n";
        $work[] = $p_array;
        $work[] = $s_array;
    }
    $maze .= '1'.implode('', array_shift($work))."1\n";
    $maze .= $l_array."\n";
    $maze = strtr($maze, array('1'=>'■', '0'=>'　'));

    return $maze;
}

function wall(&$work, $row, $col)
{
    $w = array();
    if ($row == 0 && $work[0][$col*2+1] == '0') {
        $w[] = array(0, $col*2+1);
    }
    if ($work[1][$col*2+2] == '0') {
        $w[] = array(1, $col*2+2);
    }
    if ($work[2][$col*2+1] == '0') {
        $w[] = array(2, $col*2+1);
    }
    if ($work[1][$col*2] == '0') {
        $w[] = array(1, $col*2);
    }
    shuffle($w);
    $work[$w[0][0]][$w[0][1]] = '1';
}
?>

壁伸ばし法の変種ですね。

> ちなみに棒倒し法なんかだと、例えば次のようなものを生成できません。

棒倒し法では生成方向に逆行する経路が出来ないという意味でしょうか？

ルールについてよくわからないので質問します。
ルール１を満たさないのは、どういう場合ですか？
ルール２を満たさないのは、どういう場合ですか？
このプログラムがルールを満たしているということは、壁か、通路か未定の部分をあらかじめ
どちらかに固定した部分があってもよいということですか？
このプログラムを他の投稿プログラムと区別しているようにみえますが、ルール以外に
区別する「なにか」があるのですか？

このアルゴリズムで組んでみました。Pentium2 266MHzで30秒です。きっともっと最適化の余地があることでしょう。。。。

#include <vector>
#include <fstream>
#include <algorithm>
#include <cstdlib> // random, srand
#include <cassert> // assert
#include <ctime> // time

#define REP(i, b, e) for (size_t i = b; i < e; ++i)
#define STEP(i, b, e, step) for (size_t i = b; i < e; i += step)

const size_t wall = static_cast<size_t>(-1);

bool random()
{
    return std::rand() < RAND_MAX / 2;
}

void print(std::ostream& out, const std::vector<size_t>& map)
{
    REP(i, 0, map.size())
    {
        out << (map[i] == wall ? "¡" : "@");
    }

    out << std::endl;
}

void create_maze(const char* path, size_t n, size_t m)
{
    assert(n >= 1); assert(m >= 1);

    std::ofstream out(path);

    std::vector<size_t> areas(n); // identifers of areas

    REP(i, 0, n) areas[i] = i;

    std::vector<size_t> map(2 * n + 1, wall);

    print(out, map);

    for (--m; ; --m)
    {
        STEP(i, 1, 2 * n, 2) if (map[i] == wall)
        {
            assert(! areas.empty());

            map[i] = areas.back();

            areas.pop_back();
        }

        STEP(i, 2, 2 * n, 2) if (map[i - 1] != map[i + 1] && (m == 0 || random()))
        {
            const size_t old_area = map[i - 1];

            const size_t new_area = map[i + 1];

            areas.push_back(old_area);

            std::replace(map.begin(), map.end(), old_area, new_area); // caution! passed by reference

            map[i] = new_area;
        }

        print(out, map);

        if (m == 0)
        {
            break;
        }

        STEP(i, 2, 2 * n, 2)
        {
            map[i] = wall;
        }

        std::vector<size_t> count(n, 0);

        STEP(i, 1, 2 * n, 2)
        {
            ++count[map[i]];
        }

        STEP(i, 1, 2 * n, 2) if (count[map[i]] >= 2 && random())
        {
            --count[map[i]]; map[i] = wall;
        }

        print(out, map);
    }

    print(out, std::vector<size_t>(2 * n + 1, wall));
}

int main()
{
    std::srand(std::time(NULL));

    create_maze("result.txt", 1024, 1024);
}

最適化の余地があるというのは、アルゴリズムにではなく、私のコードに、です。念のため(^^;

棒倒し方では, 格子状に壁を生成し, それを起点に周
囲に1つ以上の壁を生成していきます. 
そのため, 必ず格子状に壁が存在し, かつその周辺に
1つ以上壁が存在することになり, 一部の構造の迷路
が生成できないということなんだと思います.

ごめんなさい。ルールわかりにくかったですね。

> ルール１を満たさないのは、どういう場合ですか？

1. 格子状の迷路であること
このルールは立体交差、斜め経路、グニャグニャ経路等
を作らないでほしいという意図で作ったルールです。

> ルール２を満たさないのは、どういう場合ですか？

2. 経路の幅は均等であること。
このルールは以下のような迷路を作らないでほしいとい
う意図で作ったルールです。
■■■■■■■■■■■
■　　　　　　　■　■
■　ド　■　■■■　■
■　ォ　■　■　　　■
■　ォ　■■■■■　■
■　ン　■　　　　　■
■　！　■　■　広　■
■　　　■　■　過　■
■　■　■　■　ぎ　■
■　■　　　■　　　■
■■■■■■■■■■■

> このプログラムがルールを満たしているということは、
> 壁か、通路か未定の部分をあらかじめどちらかに固定
> した部分があってもよいということですか？

そのとおりです。
あらかじめの固定を禁止するルールを作らなかったのを
後悔しています(笑)

とはいえ、解いて面白い迷路が出来上がるなら固定もア
リかなと思ってます。
その点katsuさんのプログラムが作り出す迷路はあんまり
面白くなさそうなのでちょっと残念です。

> このプログラムを他の投稿プログラムと区別している
> ようにみえますが、ルール以外に区別する「なにか」
> があるのですか？

評価した人ごとに理由があると思いますが、おそらく
　・解いて面白い迷路を作るべき
　・固定を禁止するルールがある
といった思い込みを持っていたところに、思い込みに反
した解決策が示されて、
　「こりゃ一本とられたよ」
という気持ちが他の投稿プログラムと区別してるんじゃ
ないでしょうか？

C++, Pentium2 266MHzで30秒ですか。

私の使ったPentiumM 2100MHzとの性能差を約10倍とすると。
(クロック差8倍とメモリとかキャッシュとかで+2倍)
13秒ぐらいで生成できそうなんですが・・・。

あ、そういえば速度を計ったときには出力コードをコメント
にしてました。

純粋にバッファ操作の時間だけ計測すると何秒ぐらいになり
ますか？

// こんな感じで。
void print(std::ostream& out, const std::vector<size_t>& map)
{
    REP(i, 0, map.size())
    {
//      out << (map[i] == wall ? "■" : "　");
    }

//  out << std::endl;
}

23秒でした。ていうか、私のコード、日本語部分が化けてますね。すみません（汗）

#日ごろ秀丸＋欧文フォントで組んでるので、そのままコピーペーストするとこうなる

> 23秒でした。

（・３・）アルェー？
速くなったけど13秒には及ばないですね。
いくつもあるループを統合したら改善するのかも。

-------------
　STEP(x) {
　	A
　}

　STEP(x) {
　	B
　}
-------------

　　↓

-------------
　STEP(x) {
　	A
　	B
　}
-------------

> #日ごろ秀丸＋欧文フォントで組んでるので、
> そのままコピーペーストするとこうなる

シブイ！
Courierでしょうか？

私はプロポーショナルフォント(英字Tahoma + 日本語MSUIGothic)で
プログラムしてます。
周りからは変態呼ばわりされてます(笑)

棒倒し法の問題点は以下のようです。

1. 一行目に壁が少なくなってしまう。
2. 閉じた領域が出来てしまう。
3. 全ての道と連絡する抜け道ができてしまう。
4. 隙間だらけになってしまう。
5. 生成方向に逆行する経路ができない。

1～4の問題を克服した発散棒倒し法が紹介されていますが、
放射状に迷路を作るのでO(n)で実装するのは無理かもしれません。

参考
迷路自動生成アルゴリズム「発散棒倒し法」
http://aoyzsas.hp.infoseek.co.jp/maze/maze_hpillar.html

>速くなったけど13秒には及ばないですね。

うーん、コンパイラが違うとか。g++ -O2 でコンパイルしました。まあ、色々古いパソコンなので他にも原因があるかも。

>シブイ！
>Courierでしょうか？

Courier Newです（笑）

>私はプロポーショナルフォント(英字Tahoma + 日本語MSUIGothic)で
>プログラムしてます。
>周りからは変態呼ばわりされてます(笑)

・・・変態（ぼそ）(^^;

> 壁伸ばし法の変種
やってることはグラフの最小全域木を求めるPrimのアルゴリズムと同じですね。
壁が枝に対応します。

> 棒倒し法では生成方向に逆行する経路が出来ないという意味でしょうか？
生成方向に逆行するような棒の倒し方ができないので、
4方向全てに倒す必要のある迷路は、どの方向から始めても
無理なのではないかと考えました。

>グラフの最小全域木を求めるPrimのアルゴリズムと同じ

たしかに「ループがない」「たどり着けない場所がない」という条件はまさに全域木！

えーと、木に見たててるのは壁の方なのですが、
確かに通路の全域木を作る方が素直ですね(笑)

というわけで、通路の最小全域木を作るものを実装してみました。穴掘りです。

Pentium4/2.8GHzで1分半ほど。

class Maze
  WALL, VAC = '#', ' '
  DIRS = [[+1, 0], [-1, 0], [0, +1], [0, -1]]
  def initialize(m, n)
    @rows = m
    @cols = n
    @field = Array.new(2*@rows+1) { WALL*(2*@cols+1) }
  end

  def gen
    conn = Array.new(@rows) { Array.new(@cols, false) }
    cand = [[rand(@rows), rand(@cols), 0, 0]] # (0,0) is dummy
    until cand.empty?
      y, x, dy, dx = cand.slice!(rand(cand.size))
      next if conn[y][x]
      conn[y][x] = true
      @field[2*y+1-dy][2*x+1-dx] = VAC
      @field[2*y+1][2*x+1] = VAC
      DIRS.each do |mv|
        y_, x_ = y+mv[0], x+mv[1]
        if (0...@rows) === y_ &&
           (0...@cols) === x_ &&
           !conn[y_][x_]
          cand << [y_, x_, mv[0], mv[1]]
        end
      end
    end
    self
  end

  def p
    puts @field
  end
end

M, N = 10, 10
maze = Maze.new(M, N)
maze.gen.p

私の方もうまく聞きたいことを伝えられないようで。
もうすこしだけ。下の例は、どうなりますか？
１　　　　　　　　　２　　　　　　　　　３
■■■■■　　■■■■■　　■■■■■
■□□□■　　■□■■■　　■□□□■
■■□■■　　■□■■■　　■□□□■
■□□□■　　■□□□■　　■□□□■
■■■■■　　■■■■■　　■■■■■

４
■■■■■■■■■■■
■□□□■□□□□□■
■□□□■□□□□□■
■□□□■□□□□□■
■□□□■■■□□□■
■□□□□□□□□□■
■□□□□□□□□□■
■□□□□□□□□□■
■■■■■■■■■■■

なんか空白にすると詰まってしまうので□にしました。

> もうすこしだけ。下の例は、どうなりますか？

あ～。理解しました。

下の大きさの迷路の場合、★の位置が必ず柱(通過不能)になることを望んでいます。
■■■■■■■■■■■
■□□□□□□□□□■
■□★□★□★□★□■
■□□□□□□□□□■
■□★□★□★□★□■
■□□□□□□□□□■
■□★□★□★□★□■
■□□□□□□□□□■
■■■■■■■■■■■
自分でも「格子状」っていう言葉を深く考えてませんでした。

また、塗りつぶされた領域ができないことも望んでいます。
■■■■■■■■■■■
■□□□□□□□■■■
■□■■■■■■■■■
■□■■■□■■■■■
■□■■■□■■■■■
■□□□□□□□□□■
■□★□★□★□★□■
■□□□□□□□□□■
■■■■■■■■■■■
こんなんとかダメです。
これは、到達不可能な箇所を壁にしてお茶を濁したと見ることもできますね。

ルールにボロが出てますね・・・orz
それでも、多くの人には一応意図が伝わってたみたいでよかった。

すばやい回答ありがとうございます。
やっとわかりました。

Squeak Smalltalk で。

n = 1024、m = 1024 では、1 GHz PowerPC (OS X) で６分半ほどでした。

| Ｎ Ｍ 時間 出力 ライン 直前向き 上下枠描画 |
Ｎ := 1024.  Ｍ := 1024.

時間 := [
    出力 := FileStream forceNewFileNamed: 'doukaku123.out'.
    ライン := Array new: Ｎ.
    直前向き := nil.
    1 to: Ｎ do: [:idx |
        | 向き |
        向き := (直前向き = #右 ifTrue: [#(上 下 右)] ifFalse: [#(上 下 右 左)]) atRandom.
        ライン at: idx put: (直前向き := 向き)].
    (上下枠描画 := [出力 nextPutAll: (String new: Ｎ + 1 * 2 + 1 withAll: $■); cr]) value.
    出力 nextPutAll: '■　'.
    ライン do: [:向き | 出力 nextPutAll: (向き = #上 ifTrue: ['■　'] ifFalse: ['　　'])].
    出力 nextPut: $■; cr.
    Ｍ timesRepeat: [
        出力 nextPut: $■.
        直前向き := nil.
        ライン do: [:向き |
            出力 nextPut: ((直前向き = #右 or: [向き = #左]) ifTrue: [$■] ifFalse: [$　]).
            出力 nextPut: $■.
            直前向き := 向き].
        出力 nextPutAll: (直前向き = #右 ifTrue: ['■■'] ifFalse: ['　■']); cr.
        出力 nextPutAll: '■　'.
        ライン do: [:向き | 出力 nextPutAll: (向き = #下 ifTrue: ['■　'] ifFalse: ['　　'])].
        出力 nextPut: $■; cr.
        直前向き := nil.
        1 to: Ｎ do: [:idx |
            | 向き |
            向き := (直前向き = #右 ifTrue: [#(下 右)] ifFalse: [#(下 右 左)]) atRandom.
            ライン at: idx put: (直前向き := 向き)]].
    上下枠描画 value] timeToRun.
"出力 edit."
^時間 milliSeconds   "=> 0:00:06:29.346 "

まだC#のコードがない様なので、遅すぎて恥ずかしいのを我慢して投稿します。

OS:Windows XP Home SP2 CPU:AMD Sempron 3400+ 1.99GHz メモリ:480MB

ファイルへの出力で15分から1時間位の間で変動するようです。

掘った方向をメモして枝切りすればもう少し速くなるかも。

see: 迷路自動生成アルゴリズム

//http://ja.doukaku.org/123/　投稿用
using System;
using System.Collections.Generic;
using System.Text;
class Program {
    static void Main(string[] args) {
        long tick = DateTime.Now.Ticks;
        const int X = 0;
        const int Y = 1;
        int xSize = int.Parse(args[0]);
        int ySize = int.Parse(args[1]);
        Random rnd = new Random();
        //注目点初期化
        int x = rnd.Next(0, xSize - 1) * 2 + 1;
        int y = rnd.Next(0, ySize - 1) * 2 + 1;
        List<int[]> canDigRoard = new List<int[]>();//注目点とすることが出来るセル
        bool[,] maze = new bool[xSize * 2 + 1, ySize * 2 + 1];//迷路データ　trueが道、falseが壁
        //全部壁にする
        for(int i = 0; i < maze.GetLength(X); i++) {
            for(int j = 0; j < maze.GetLength(Y); j++) {
                maze[i, j] = false;
            }
        }
        maze[x,y] = true;
        canDigRoard.Add(new int[] { x, y });
        //メインループ
        while(true) {
            int[][] directionList = new int[][] { 
                new int[] { -1, 0 }, 
                new int[] { 1, 0 }, 
                new int[] { 0, -1 }, 
                new int[] { 0, 1 } };
            int directionListLast = directionList.Length - 1;
            int[] direction;//方向
            do {
                int directionListIndex = rnd.Next(directionListLast);
                direction = directionList[directionListIndex];
                directionList[directionListIndex] = directionList[directionListLast--];
                if(maze.GetLength(X) > x + direction[X] * 2 && maze.GetLength(Y) > y + direction[Y] * 2 &&
                    x + direction[X] * 2 >= 0 && y + direction[Y] * 2 >= 0) {//インデックスが範囲内か判定
                    if(!(maze[x + direction[X] * 2, y + direction[Y] * 2])) {//2マス先が道かどうか
                        maze[x + direction[X], y + direction[Y]] = true;
                        maze[x + direction[X] * 2, y + direction[Y] * 2] = true;
                        canDigRoard.Add(new int[] { x + direction[X] * 2, y + direction[Y] * 2 });
                        break;
                    }
                }
            } while(directionListLast != -1);
            if(directionListLast == -1){
                for(int i = 0; i < canDigRoard.Count; i++) {
                    if(canDigRoard[i][X] == x && canDigRoard[i][Y] == y) {
                        canDigRoard.RemoveAt(i);
                    }
                }
                if(canDigRoard.Count == 0) break;
                int canDigRoardIndex = rnd.Next(0, canDigRoard.Count - 1);
                x = canDigRoard[canDigRoardIndex][X];
                y = canDigRoard[canDigRoardIndex][Y];
            } else {
                x += direction[X] * 2;
                y += direction[Y] * 2;
            }
        }
        string time = (DateTime.Now.Ticks - tick) / 10000L + "ms";
        //出力
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < maze.GetLength(Y); i++) {
            for(int j = 0; j < maze.GetLength(X); j++) {
                sb.Append(maze[j, i] ? "　" : "■");
            }
            sb.AppendLine();
        }
        Console.WriteLine(sb + time);
        Console.ReadLine();
    }
}

悔しいので書き直しました。穴掘り法ですが、前のコードは前進出来なくなったときにランダムに戻ってましたが、掘った履歴を保存しているList<T>の、特にRemove()のパフォーマンスが悪いので Stack<T>に置き換えて、ランダムではなく一つ前に戻るようにしました。

引数に、画面に収まる迷路のサイズを指定して、 36、37行目の //Out(_maze, x, y); //System.Threading.Thread.Sleep(100); と 62行目の //Console.Clear(); のコメントを外すと、モグラﾀｿ(●)が掘っている様子をリアルタイムで表示します。w

OS:Windows XP Home SP2 CPU:AMD Sempron 3400+ 1.99GHz メモリ:480MB 迷路生成のみ　1171ms 出力こみ　1750ms(ファイルへ出力)

C#ﾀｿだってやれば出来る子なんですぅ！

using System;
using System.Collections.Generic;
using System.Text;

class Class1 {
    static void Main(string[] args) {
        long tick = DateTime.Now.Ticks;
        bool[,] maze = new bool[int.Parse(args[0]) * 2 + 3, int.Parse(args[1]) * 2 + 3];
        for(int y = 0; y < maze.GetLength(1); y++) {
            for(int x = 0; x < maze.GetLength(0); x++) {
                maze[x, y] = x == 0 || y == 0 || x == maze.GetLength(0) - 1 || y == maze.GetLength(1) - 1;
            }
        }
        モグラﾀｿ mogura = new モグラﾀｿ(maze);
        string time = (DateTime.Now.Ticks - tick) / 10000L + "ms";
        mogura.Out(maze);
        Console.WriteLine("迷路生成のみ　" + time);
        Console.Write("出力こみ　" + ((DateTime.Now.Ticks - tick) / 10000L) + "ms");
        Console.ReadLine();
    }
}

class モグラﾀｿ {
    Random rnd = new Random();
    bool[,] _maze;
    Stack<int[]> line;
    public モグラﾀｿ(bool[,] maze) {
        _maze = maze;
        line = new Stack<int[]>(_maze.Length);
        Dig(2, 2);
    }

    private void Dig(int x_, int y_) {
        int x = x_, y = y_;
        while(true) {
            //Out(_maze, x, y);
            //System.Threading.Thread.Sleep(100);
            _maze[x, y] = true;
            List<int[]> direcList = new List<int[]>();
            if(!_maze[x, y - 2]) direcList.Add(new int[] { 0, -1 });
            if(!_maze[x - 2, y]) direcList.Add(new int[] { -1, 0 });
            if(!_maze[x, y + 2]) direcList.Add(new int[] { 0, 1 });
            if(!_maze[x + 2, y]) direcList.Add(new int[] { 1, 0 });
            int[] direc;
            if(direcList.Count == 0) {
                if(line.Count == 0) break; ;
                int[] back = line.Pop();
                x = back[0];
                y = back[1];
                continue;
            } else if(direcList.Count == 1) direc = direcList[0];
            else direc = direcList[rnd.Next(0, direcList.Count)];

            _maze[x + direc[0], y + direc[1]] = true;
            x += direc[0] * 2;
            y += direc[1] * 2;
            line.Push(new int[] { x, y });
        }
    }
    
    private void Out(bool[,] maze, int x_, int y_) {
        //Console.Clear();
        StringBuilder sb = new StringBuilder();
        for(int y = 1; y < maze.GetLength(1) - 1; y++) {
            for(int x = 1; x < maze.GetLength(0) - 1; x++) {
                if(x_ == x && y_ == y) { 
                    sb.Append("●");
                } else {
                    sb.Append(maze[x, y] ? "　" : "■");
                }
            }
            sb.AppendLine();
        }
        Console.WriteLine(sb);
    }
    public void Out(bool[,] maze) {
        Out(maze, -1, -1);
    }
}

VC++2005EEのコマンドラインで/EHscオプションを指定してコンパイル、実行したら時々こんな感じで掘り残しがあるのは仕様でしょうか？　■■■■■■■　■　■　■■■■■■■　■■ 　■　■　　　　　■　　　■　　　　　　　■ 　■　■　■■■■■■■■■　■■■■■■■■ 　　　■　　　　　　　　　■　■ 　■■■■■■■　■■■　■　■　■■■■■ 　■　　　■　■　　　■　　　■　■■■　■ ■■　■　■　■　■■■■■■■　■■■　■■ 　　　■　　　■　　　　　　　■ 　■■■■■　■■■■■　■　■■■■■■■ 　　　■　　　　　　　■　■　■ ■■　■　■■■■■　■■■　■　■■■■■■ 　■　■　■　　　　　■　　　■　■　■ 　■■■　■■■　■　■　■■■　■　■　■■ 　　　　　■　　　■　■　　　■　■　■ ■■　■■■■■　■■■　■　■　■　■■■■ 　　　■■■■■　■　　　■　■ ■■■■■■■■■■　■■■　■■■■■■■ 　　　　　　　　　　　■　■　■　　　　　■ 　■■■■■■■■■■■　■　■　■　■■■ (1024*1024の実行結果からコピペ)

VC++2005EEのコマンドラインで/EHscオプションを指定してコンパイル、実行したら時々こんな感じで掘り残しがあるのは仕様でしょうか？
　■■■■■■■　■　■　■■■■■■■　■■
　■　■　　　　　■　　　■　　　　　　　■　
　■　■　■■■■■■■■■　■■■■■■■■
　　　■　　　　　　　　　■　■　　　　　　　
　■■■■■■■　■■■　■　■　■■■■■　
　■　　　■　■　　　■　　　■　■■■　■　
■■　■　■　■　■■■■■■■　■■■　■■
　　　■　　　■　　　　　　　■　　　　　　　
　■■■■■　■■■■■　■　■■■■■■■　
　　　■　　　　　　　■　■　■　　　　　　　
■■　■　■■■■■　■■■　■　■■■■■■
　■　■　■　　　　　■　　　■　■　■　　　
　■■■　■■■　■　■　■■■　■　■　■■
　　　　　■　　　■　■　　　■　■　■　　　
■■　■■■■■　■■■　■　■　■　■■■■
　　　■■■■■　■　　　■　■　　　　　　　
■■■■■■■■■■　■■■　■■■■■■■　
　　　　　　　　　　　■　■　■　　　　　■　
　■■■■■■■■■■■　■　■　■　■■■　
(1024*1024の実行結果からコピペ)

ルール的には堀残しはNGです。

C++のコンパイル環境がないので実行して確認できませんが、バグがあるのかもしれませんね。

なんとなく、
 std::random_shuffle(U.Char,U.Char+4);
あたりが怪しそうです。
C++のコード追うのは苦手orz

無難に棒倒し法です。

CPU：Intel Core 2 Duo CPU 2.00GHz メモリ：2046MB OS：Windows Vista Home Basic

class Program
{
    static void Main(string[] args)
    {
        randomMeiro(1024, 1024);
        Console.ReadLine();
    }

    public static void randomMeiro(int m, int n)
    {
        //変数
        long start = DateTime.Now.Ticks;
        Random rand = new Random(DateTime.Now.Millisecond);
        n = 2 * n;
        m = 2 * m;

        //データ生成
        bool[,] map = new bool[n + 1, m + 1];
        for (int i = 0; i <= n; i++)
        {
            for (int j = 0; j <= m; j++)
            {
                if (j == 0 || i == 0 || i == n || j == m || (i % 2 == 0 && j % 2 == 0) ) map[i, j] = true;
                else map[i, j] = false;
            }
        }

        //迷路生成
        for (int i = 2; i < n; i += 2)
        {
            for (int j = 2; j < m; j += 2)
            {
                int max = 2;
                if (i == 2) max++;
                int x = i;
                int y = j;
                switch (rand.Next(0, max))
                {
                    case 0: x++; break;
                    case 1: y++; break;
                    case 2: x--; break;
                    case 3: y--; break;
                }
                if (map[x, y]) j -= 2;
                else map[x, y] = true;
            }
        }
        Console.WriteLine("ファイル出力無：" + ((DateTime.Now.Ticks - start) / 10000L) + "ms");

        //表示
        using (StreamWriter sw = new StreamWriter(@"meiro.dat"))
        {
            for (int i = 0; i <= n; i++)
            {
                for (int j = 0; j <= m; j++)
                {
                    if (map[i, j]) sw.Write("■");
                    else sw.Write("　");
                }
                sw.WriteLine();
            }
        }

        Console.WriteLine("ファイル出力有：" + ((DateTime.Now.Ticks - start) / 10000L) + "ms");
    }
}

やばい、時間を書き忘れました…
ファイル出力無：170ms
ファイル出力有：463ms

初投稿です。
格子点をdisjoint setとして管理し、でたらめな順序で壁を立てていく方法です。

実行時間は、5回の実行で以下のとおりでした。
6.063, 6.546, 5.968, 6.188, 6.172 (秒)
[CoreSolo U1300 (1.06GHz), 512MB memory] (Panasonic Let's note CF-R5)

import java.util.ArrayList;
import java.util.List;

public class Maze {

    private static class Pole {
        Pole parent;
        Pole() { this.parent = this; }
        Pole getRoot() {
            return (parent == this ? this : (parent = parent.getRoot()));
        }
    }

    private static class Point {
        int x;
        int y;
        Point(int x, int y) { this.x = x; this.y = y; }
    }

    private int w;
    private int h;
    private boolean[][] hWalls;
    private boolean[][] vWalls;
    private Pole[][] poles;
    private Pole pTL;
    private Pole pBR;
    private List<Point> buildSequence;

    public Maze(int w, int h) {
        this.w = w;
        this.h = h;
    }

    public void build() {
        initialize();
        for (Point p : buildSequence) {
            buildWall(p);
        }
    }

    public void initialize() {
        initializeWalls();
        initializePolls();
        initializeBuildSequence();
    }

    private void initializeWalls() {
        hWalls = new boolean[w / 2][h / 2 - 1];
        vWalls = new boolean[w / 2 - 1][h / 2];
    }

    private void initializePolls() {
        poles  = new Pole[w / 2 + 1][h / 2 + 1];
        int pw = poles.length;
        int ph = poles[0].length;
        for (int x = 0; x < pw; x++) {
            for (int y = 0; y < ph; y++) {
                poles[x][y] = new Pole();
            }
        }
        pTL = poles[0][0];
        pBR = poles[pw - 1][ph - 1];
        for (int x = 1; x < pw; x++) {
            poles[x][0].parent = pTL;
            poles[pw - 1 - x][ph - 1].parent = pBR;
        }
        for (int y = 1; y < ph - 1; y++) {
            poles[pw - 1][y].parent = pTL;
            poles[0][ph - 1 - y].parent = pBR;
        }
    }

    private void initializeBuildSequence() {
        buildSequence = new ArrayList<Point>();
        for (int x = 1; x < w - 1; x += 2) {
            for (int y = 2; y < h - 2; y += 2) {
                buildSequence.add(new Point(x, y));
            }
        }
        for (int x = 2; x < w - 2; x += 2) {
            for (int y = 1; y < h - 1; y += 2) {
                buildSequence.add(new Point(x, y));
            }
        }
        for (int i = 0; i < buildSequence.size(); i++) {
            int j = (int) (Math.random() * buildSequence.size());
            Point pTmp = buildSequence.get(i);
            buildSequence.set(i, buildSequence.get(j));
            buildSequence.set(j, pTmp);
        }
    }

    public void buildWall(Point p) {
        Pole p1 = poles[p.x / 2][p.y / 2];
        Pole p2 = poles[(p.x + 1) / 2][(p.y + 1) / 2];
        if (isConnectable(p1, p2)) {
            if (p.x % 2 == 0) {
                vWalls[p.x / 2 - 1][p.y / 2] = true;
            } else {
                hWalls[p.x / 2][p.y / 2 - 1] = true;
            }
        }
    }

    private boolean isConnectable(Pole p1, Pole p2) {
        Pole r1 = p1.getRoot();
        Pole r2 = p2.getRoot();
        if (r1 == r2) {
            return false;
        } else {
            Pole rTL = pTL.getRoot();
            Pole rBR = pBR.getRoot();
            if (r1 == rTL && r2 == rBR || r1 == rBR && r2 == rTL) {
                return false;
            } else {
                r2.parent = r1;
                return true;
            }
        }
    }

    public boolean isWall(int x, int y) {
        if (x == 0 || x == w - 1 || y == 0 || y == h - 1) {
            return true;
        } else if (x % 2 == 0 && y % 2 == 1) {
            return vWalls[x / 2 - 1][y / 2];
        } else if (x % 2 == 1 && y % 2 == 0) {
            return hWalls[x / 2][y / 2 - 1];
        } else {
            return x % 2 == 0;
        }
    }

    public static void main(String args[]) {
        int w = Integer.parseInt(args[0]) * 2 + 1;
        int h = Integer.parseInt(args[1]) * 2 + 1;
        long begin = System.currentTimeMillis();
        Maze maze =    new Maze(w, h);
        maze.build();
        long end = System.currentTimeMillis();
        System.out.println("Elapsed time: " + (end - begin) / 1000.0 + " sec.");
        // print(maze);
    }

    private static void print(Maze maze) {
        for (int y = 0; y < maze.h; y++) {
            for (int x = 0; x < maze.w; x++) {
                System.out.print(maze.isWall(x, y) ? '■' : '　');
            }
            System.out.println();
        }
    }
}

Haskellでやってみました。学習中です。とても楽しい問題ですね！

地道にスタート地点からほり続けるアルゴリズムです。

最初はData.Array.Arrayを使いました。ヒープ爆発で没。その後、UArrayを使い、多少改善、
最終的にはIOUArrayに落ち着きました。

その他のメモリ消費・速度対策としては
１．何度も計算する必要のないものを定数化する。
２．深さ優先の再帰から広さ優先の再帰にする。かつ、TailRecursionにした。
３．元の実装は迷路中の位置をすべてタプル（ｘ、ｙ）で表現していたので、配列アクセスのときにインデックスへの
変換が多発していた。ので、インデックスベースの計算の高度も少し書きました。
４．迷路のサイズのグローバル変数化

GHCのプロファイラをはじめて使いました。

結果として、
-- Vista Ultimate on Toshiba Portege M200 (Centrino Duo)
--try 1 Elapsed Time :  00:00:05.760
--try 2 Elapsed Time :  00:00:05.787
--try 3 Elapsed Time :  00:00:05.790
といった結果が出ています。

出題の方のコメントのうち、「。限られたメモリを使って縦方向に無限に広い迷路を…」の部分のヒントは
利用していません…使えば、まだまだ早くなると思うのですが、アルゴリズム的なショートカットではないかたちで、
ほかにどんなテクニックで高速化ができるかに興味があります。
考えたけどやってないもののひとつとしては、迷路の１マスを１Bitでやってみるとか…

ほかの方のHaskellの投稿もぜひ見せてもらいたいです。何かフィードバックありましたらよろしくお願いします。

module Main
    where

import Data.Array.IO 
import Control.Monad.State
import System.Random
import Data.List    -- for intercalate

type Point = (Int, Int)
type TwoDArray = IOUArray Int Char
type Maze = TwoDArray

ptToIdx :: Point -> Int
ptToIdx (x, y) = (y * rszx) + x

rasterize :: Int -> Int
rasterize i = i * 2 + 1

rasterizePt :: Point -> Point
rasterizePt (x, y) = (rasterize x, rasterize y)

lstMappedPoint :: Point -> [Point] -> [Point]
lstMappedPoint pt pts = map (addPt pt) pts 
    where
        addPt (x1, y1) (x2, y2) = (x1 + x2, y1 + y2)

lstMappedIdx :: Int -> [Int] -> [Int]
lstMappedIdx idx idxs = map (idx +) idxs 


inBoundForMove :: Point -> Bool
inBoundForMove (x, y)
    | x <= 0 || x + 1 >= rszx || y <= 0 || y + 1 >= rszy = False
    | otherwise = True

surroundingsIdx :: Point -> [Int]
surroundingsIdx (x, y)
    | x == 0        && y == 0        =                               nbIdxsTopLeft
    | x == rszx - 1 && y == 0        =                               nbIdxsTopRightMapped
    | x == 0        && y == rszy - 1 =                               nbIdxsBottomLeftMapped 
    | x == rszx - 1 && y == rszy - 1 =                               nbIdxsBottomRightMapped 
    | x == 0                         = lstMappedIdx (ptToIdx (x, y)) nbIdxsLeft
    | x == rszx - 1                  = lstMappedIdx (ptToIdx (x, y)) nbIdxsRight
    |                  y == 0        = lstMappedIdx (ptToIdx (x, y)) nbIdxsTop
    |                  y == rszy - 1 = lstMappedIdx (ptToIdx (x, y)) nbIdxsBottom
    | otherwise                      = lstMappedIdx (ptToIdx (x, y)) nbIdxs

onTheSameLineIdx :: [Int] -> Bool
onTheSameLineIdx [] = True
onTheSameLineIdx [i] = True
onTheSameLineIdx (idx:idxs) = (all (sameX idx) idxs) || (all (sameY idx) idxs)
    where
        sameX idx1 idx2 = (abs $ idx1 - idx2) <= 2
        sameY idx1 idx2 = (abs $ idx1 - idx2) == rszy || (abs $ idx1 - idx2) == rszy * 2

left  =[0..1]    :: [Int]
right =[-1..0]    :: [Int]
top   =[0..1]    :: [Int]

bottom=[-1..0]    :: [Int]
rest  =[-1..1]    :: [Int]

nbptsTopLeft     = [(x, y) | x <- left,  y <- top,    x /= 0 || y /= 0]    :: [Point]
nbptsTop         = [(x, y) | x <- rest,  y <- top,    x /= 0 || y /= 0]    :: [Point]
nbptsTopRight    = [(x, y) | x <- right, y <- top,    x /= 0 || y /= 0]    :: [Point]
nbptsLeft        = [(x, y) | x <- left,  y <- rest,   x /= 0 || y /= 0]    :: [Point]
nbpoints         = [(x, y) | x <- rest,  y <- rest,   x /= 0 || y /= 0]    :: [Point]
nbptsRight       = [(x, y) | x <- right, y <- rest,   x /= 0 || y /= 0]    :: [Point]
nbptsBottomLeft  = [(x, y) | x <- left,  y <- bottom, x /= 0 || y /= 0]    :: [Point]
nbptsBottom      = [(x, y) | x <- rest,  y <- bottom, x /= 0 || y /= 0]    :: [Point]
nbptsBottomRight = [(x, y) | x <- right, y <- bottom, x /= 0 || y /= 0]    :: [Point]

nbIdxsTopLeft     = map ptToIdx nbptsTopLeft
nbIdxsTop         = map ptToIdx nbptsTop
nbIdxsTopRight    = map ptToIdx nbptsTopRight
nbIdxsLeft        = map ptToIdx nbptsLeft
nbIdxs            = map ptToIdx nbpoints
nbIdxsRight       = map ptToIdx nbptsRight
nbIdxsBottomLeft  = map ptToIdx nbptsBottomLeft
nbIdxsBottom      = map ptToIdx nbptsBottom
nbIdxsBottomRight = map ptToIdx nbptsBottomRight

nbIdxsTopRightMapped    = lstMappedIdx (ptToIdx(rszx - 1, 0)) nbIdxsTopRight
nbIdxsBottomLeftMapped  = lstMappedIdx (ptToIdx(0, rszy- 1)) nbIdxsTopRight
nbIdxsBottomRightMapped = lstMappedIdx (ptToIdx(rszx - 1, rszy- 1)) nbIdxsTopRight

movable :: Point -> Bool
movable (x, y)  = (abs x) + (abs y) == 1

nbmovables :: [Point]
nbmovables = filter (movable) nbpoints

nbmovablesIdx :: [Int]
nbmovablesIdx = map ptToIdx nbmovables

potentialMoves :: Point -> [Point]
potentialMoves pt = lstMappedPoint pt nbmovables

initialMaze :: IO TwoDArray
initialMaze = newArray (0, rcmz) 'x'

dig :: TwoDArray -> Point -> IO()
dig rg pt = do
    writeArray rg (ptToIdx pt) ' '

fetchIdx :: TwoDArray -> Int -> IO Char
fetchIdx rg idx = readArray rg idx

fetch :: TwoDArray -> Point -> IO Char
fetch rg pt = readArray rg (ptToIdx pt)

idxHas :: Maze -> Int -> IO Bool
idxHas mz idx = do
    chT <- fetchIdx mz idx
    return $ chT == ' '

lookaround :: Maze -> Point -> IO Bool
lookaround mz pt = do
    filteredPoints <- filterM (idxHas mz) $ surroundingsIdx pt
    return $ onTheSameLineIdx filteredPoints

legalMove :: Maze -> Point -> IO Bool
legalMove mz pt = do
        ch <- fetch mz pt
        if ch == 'x' then
            lookaround mz pt
            else
                return False

moves :: Point -> [Point]
moves pt = filter (inBoundForMove) $ potentialMoves pt

diggableNbr :: Point -> Point -> Bool
diggableNbr (x1, y1) (x2, y2) = ((abs $ x1 - x2) + (abs $ y1 - y2)) == 1

genMaze :: Maze -> [Point] -> IO()
genMaze mz pts = doRecurse pts
    where
        doRecurse :: [Point] -> IO()
        doRecurse [] = return ()
        doRecurse pts = do
            ptsDug <- mapDig pts
            doRecurse $ concatMap (moves) ptsDug

        mapDig :: [Point] -> IO [Point]
        mapDig [] = return []
        mapDig (x:xs) = do
            fDug <- digIfValid x
            if (fDug) then do
                xsRet <- mapDig xs -- $ filter (diggableNbr x) xs
                return (x:xsRet)
                else
                    mapDig xs

        digIfValid :: Point -> IO Bool
        digIfValid pt = do
            fPtValid <- legalMove mz pt
            if (fPtValid) then do
                dig mz pt
                return True
                else
                    return False

dumpRow :: TwoDArray -> Int -> IO()
dumpRow rg iy = do
    str <- mapM (readArray rg) $ [(iy * rszx)..(iy * rszx + rszx - 1)]
    putStrLn str

dumpMaze :: TwoDArray -> IO ()
dumpMaze rg = do
    mapM (dumpRow rg) [0..(rszy - 1)]
    return ()

szx = 1024 :: Int
szy = 1024 :: Int
rszx = rasterize szx
rszy = rasterize szy

cmz = szx * szy - 1
rcmz = rszx * rszy - 1

main :: IO()
main = do
    mz <- initialMaze
    x <- getStdRandom $ randomR (0, szx - 1)
    y <- getStdRandom $ randomR (0, szy - 1)
    putStrLn $ show (x, y)
    genMaze mz [rasterizePt (x, y)]
    dumpMaze mz

Perlが無かったので投稿します。棒倒し法を使いました。

#!/usr/bin/perl
use strict;
use constant {
    BLACK => "■",
    WHITE => "□",
};

my $DEBUG = 1;
my $TATE  = 1024;
my $YOKO  = 1024;
my @blocks = map{0}(0 .. ($YOKO-1)*3);

sub debug{print @_ if $DEBUG}
sub roof_floor{debug(BLACK x (2*$_[0]+1), "\n")}
sub ms_random{int(rand(4)) + ($_[0]*3)}
sub marble{
    my ($times, $ref_blocks) = @_;
    for(my $i=0; $i<$times-1; $i++){
        $ref_blocks->[2+$i*3] = 0;
        while(1){
            my $suffix = &ms_random($i);
            next if $ref_blocks->[$suffix] == 1;
            $ref_blocks->[$suffix] = 1;
            last;
        }
    }
}
sub operate_even{
    my ($times, $ref_blocks, $one_two) = @_;
    debug(BLACK, WHITE);
    for(my $i=0; $i<$times-1; $i++){
        if($ref_blocks->[$one_two+3*$i] == 1){
            debug(BLACK, WHITE);
        }
        else{
            debug(WHITE, WHITE);
        }
        $ref_blocks->[1+3*$i] = $ref_blocks->[2+3*$i];
    }
    debug(BLACK, "\n");
}
sub operate_odd{
    my ($times, $ref_blocks) = @_;
    for(my $i=0; $i<$times; $i++){
        if($ref_blocks->[$i*3] == 1){
            debug(BLACK, BLACK);
            $ref_blocks->[$i*3] = 0;
        }
        else{
            debug(BLACK, WHITE);
        }
    }
    debug(BLACK, "\n");    
}

{
    roof_floor($YOKO);
    while(--$TATE > 0){
        marble($YOKO, \@blocks);
        operate_even($YOKO, \@blocks, 1);
        operate_odd($YOKO, \@blocks);
    }
    operate_even($YOKO, \@blocks, 2);
    roof_floor($YOKO);
}

穴掘りでやっていたらスタックが溢れて破綻したので棒倒しで。
壁の厚さに -1 を指定すると、道幅と壁の厚さが一致します。0 が最小幅になります。

15cmx15cm 1024x1024 
Acrobat Distiller 8.0 プレス品質
Intel X5365(3GHz, 1 core) 

で PDF変換に 47秒でした。
なんか B0版くらいの紙に出力したい衝動が...

# 昔、256 bytes のコードで連続紙に迷路を延々
# 出力しつづけるプログラムがあったなぁ....

%!PS

/GenOneLine { % firstline_p width GenOneLine -
    gsave
    1 sub 0 [[-1 0] [0 1] [1 0] [0 -1]] 3 -1 roll
    {
        dup
        rand 3
        5 index add 4 index sub mod
        4 -1 roll add
        dup 2 eq { 1 } { 0 } ifelse
        4 1 roll
        get aload pop 0 0 moveto rlineto stroke
        1 0 translate
    } repeat
    pop pop pop
    grestore
} bind def

/GenMaze { % NumRoadX NumRoadY MazeWidth MazeHeight OffsetX OffsetY WallWidth
    gsave
    dup -1 eq {
        pop
        0.5
    } {
        6 index mul 4 index div
    } ifelse
    setlinewidth
    translate

    2 index div
    exch
    3 index div
    exch
    scale

    0 setgray
    2 setlinecap
    true setstrokeadjust

    0 0 moveto 1 index 0 lineto 2 copy lineto 0 1 index lineto closepath stroke
    1 1 translate
    1 2 index GenOneLine
    2 sub {
        0 1 translate
        dup 0 exch GenOneLine
    } repeat
    pop
    grestore
} bind def

% ========== Test Code ==========
/cm { 72 mul 2.54 div } bind def
/mm { 72 mul 25.4 div } bind def

/Arial-Black findfont 16 scalefont setfont
realtime dup srand
% size,      drawing area,    offset,     pen width
% 5 5        15 cm 15 cm      1 cm 1 cm   10 mm   GenMaze
1024 1024    15 cm 15 cm      1 cm 1 cm    0      GenMaze
10 10 moveto (Timer = ) show
realtime exch sub 1000 div 10 string cvs show ( sec) show

showpage

だいぶ動作速度を改善しました。 diff にしようかと思いましたが、あまり小さくならないので、そのままつっこみます。

%!PS

/GenOneLine { % width v firstline_p   GenOneLine   width v 3
    gsave
    0
    3 index
    {
        2 copy sub
        rand exch mod add
        2 index exch get aload pop 0 0 moveto rlineto
        1 0 translate
    } repeat
    pop pop 3
    stroke
    grestore
} bind def

/GenMaze { % NumRoadX NumRoadY MazeWidth MazeHeight OffsetX OffsetY WallWidth
    gsave

    % --- Set graphics parameters --- 
    dup -1 eq {
        pop
        0.5
    } {
        6 index mul 4 index div
    } ifelse
    setlinewidth
    translate

    2 index div
    exch 3 index div exch
    scale

    0 setgray
    2 setlinecap
    true setstrokeadjust

    % --- draw outline box ---
    0 0 moveto 1 index 0 lineto 2 copy lineto 0 1 index lineto closepath stroke
    1 1 translate
    exch 1 sub exch 2 sub
    [[0 -1 0] [0 0 1] [1 1 0] [0 0 -1]] 
    3 -1 roll exch 4
    % Y X v 4
    GenOneLine
    % Y X v 3
    4 -1 roll
    {
        % X v 3
        0 1 translate
        GenOneLine
    } repeat
    pop pop pop
    grestore
} bind def

% ========== Test Code ==========
/cm { 72 mul 2.54 div } bind def
/mm { 72 mul 25.4 div } bind def


/Arial-Black findfont 16 scalefont setfont 
realtime dup srand


% size,      drawing area,    offset,     pen width
% 10 10        15 cm 15 cm      1 cm 3 cm   5 mm   GenMaze

<< /PageSize [ 102 cm 110 cm ] >> setpagedevice
% size,      drawing area,    offset,     pen width
1024 1024    100 cm 100 cm    1 cm 3 cm    0.3 mm  GenMaze


10 mm 10 mm moveto (Timer = ) show
realtime exch sub 1000 div 10 string cvs show ( sec) show

showpage

お久しぶりです。 >>#5377 はバグです。実は投稿してから気がついて修正したんですけど、鮮度に欠ける時期だったので見送っていました。でも、ちょっと後悔したので、当時FIXしたコードを乗っけます。生成部分が幾らかコンパクトになっています。ついでに、さっき追加で生成時間を計れるようにしました。

VC2008のリリースの速度最適化でコンパイルして1024*1024を６００クロック位で生成していました。

当時の事は大分忘れているので、もう修正できません。コッソリと後悔を埋めさせてもらいます。自己満足でごめんなさい。失礼しました。

#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_;}
        Point2 operator + (Point2& in){
            Point2 T;
            T.x= x+in.x;
            T.y= y+in.y;
            return T;
        }
    };
    
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(){
        Point2 T={rand()%Width(),rand()%Height()};
        Generate(T);
    }
    
    void Generate(Point2 Pos,bool IsDifferent = false){//非再起版。
        static Point2 V[]={{-1,0},{0,1},{1,0},{0,-1}};
        Uni F;
        F.Int=0x03020100;
        std::vector<Point2> stp;//スタック。
        stp.push_back(Pos);
        std::random_shuffle(F.Char,F.Char+4);
        while(stp.size() != 0){
            Pos = stp.back();stp.pop_back();
            if(!IsDifferent) F.Int=0x03020100;
            std::random_shuffle(F.Char,F.Char+4);
                for(int i=0;i<4;i++){
                    if(ToVisit(Pos,V[F.Char[i]],F.Char[i])) stp.push_back(Pos +V[F.Char[i]]);
                }
        }
        return ;
    }
    
    bool ToVisit(Point2 Base,Point2 To,int Command){
        if(!CanVisit(Base.x,Base.y)) return false;
        if(!CanVisit(Base.x+To.x,Base.y+To.y)) return false;
        //if(AlreadyVisit(Base.x,Base.y)) return false;
        if(AlreadyVisit(Base.x+To.x,Base.y+To.y)) return false;
        MarkVisit(Base.x,Base.y);
        MarkVisit(Base.x+To.x,Base.y+To.y);
        EraseWall(Base,To,Command);
        return true;
    }
};
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));
    clock_t start,end;
    start = clock();
    //Maze_t m(12,5);
//    Maze_t m(19,11);
//    Maze_t m(19,100);
    Maze_t m(1024,1024);
    end = clock();
    printf("Generate at [%d]clock!\n",end-start);
    PrintMaze2(m);
    return 0;
}

前々から気になっていたので今更ながら挑戦してみました。棒倒し法です。


OS, マシンスペックは以下の通り。
OS: FreeBSD 7.0-STABLE
CPU: Celeron 500MHz
Mem: 320MB
…orz


バイトコードとネイティブコードを作成して性能を比べてみました。

mitsu@garlic$ ocamlfind c -package unix -linkpkg -o maze.byte maze.ml
mitsu@garlic$ ocamlfind opt -package unix -linkpkg -o maze.native maze.ml

mitsu@garlic$ time ./maze.byte 1024 1024 > /dev/null

real    0m15.978s
user    0m15.583s
sys     0m0.132s
mitsu@garlic$ time ./maze.native 1024 1024 > /dev/null

real    0m2.443s
user    0m2.367s
sys     0m0.037s
mitsu@garlic$

ネイティブコードはさすがに早いなぁ、と思いました。

あと、このマシンスペックで3秒を切っているので、まぁ良いかな、と。

let x = int_of_string (Sys.argv.(1))
let y = int_of_string (Sys.argv.(2))

let line_loop line func =
  let rec loop pos =
    if pos < x * 2 - 1 then (
      func line pos;
      loop (pos + 1)
    ) in
  loop 0

let make_line v = Array.make (x * 2 - 1) v

let make_empty_line () = make_line 0

let make_filled_line () = make_line 1

let make_checked_line () =
  let line = make_empty_line () in
  line_loop line (
    fun l p -> if (p mod 2) = 1 then l.(p) <- 1
  );
  line

let print_line line =
  print_string "■";
  line_loop line (
    fun l p -> if l.(p) = 1 then print_string "■" else print_string "　"
  );
  print_endline "■"

type mode = Top | Normal

let make_maze mode lines =
  let way = match mode with Top -> 4 | Normal -> 3 in
  let rec make_wall pos =
    let (y, x) =
      match (Random.int way) with
      | 0 -> (1, pos + 1)
      | 1 -> (2, pos)
      | 2 -> (1, pos - 1)
      | 3 -> (0, pos)
      | _ -> failwith "invalid value" in
    if lines.(y).(x) = 1 then make_wall pos else lines.(y).(x) <- 1 in
  let rec loop pos =
    if pos < x * 2 - 1 then (
      if pos mod 2 = 1 then make_wall pos; loop (pos + 1)
    ) in
  loop 0

let main () =
  let _ = Random.init (int_of_float (Unix.time ())) in
  let filled_line = make_filled_line () in
  print_line filled_line;
  let rec loop cnt last_line =
    if cnt < y
      then (
        let lines = [|last_line; make_checked_line (); make_empty_line ()|] in
        make_maze (if cnt = 0 then Top else Normal) lines;
        print_line lines.(0);
        print_line lines.(1);
        loop (cnt + 1) lines.(2)
      )
      else print_line last_line in
  loop 0 (make_empty_line ());
  print_line filled_line

let _ = main ()

壁かどうかはヴァリアントにすべきでした… 自己満足ですが修正版を。

type field = Space | Wall

let x = int_of_string (Sys.argv.(1))
let y = int_of_string (Sys.argv.(2))

let line_loop line func =
  let rec loop pos =
    if pos < x * 2 - 1 then (
      func line pos;
      loop (pos + 1)
    ) in
  loop 0

let make_line v = Array.make (x * 2 - 1) v

let make_empty_line () = make_line Space

let make_filled_line () = make_line Wall

let make_checked_line () =
  let line = make_empty_line () in
  line_loop line (
    fun l p -> if (p mod 2) = 1 then l.(p) <- Wall
  );
  line

let print_line line =
  print_string "■";
  line_loop line (
    fun l p -> if l.(p) = Wall then print_string "■" else print_string "　"
  );
  print_endline "■"

_build  maze.ml
type mode = Top | Normal

let make_maze mode lines =
  let way = match mode with Top -> 4 | Normal -> 3 in
  let rec make_wall pos =
    let (y, x) =
      match (Random.int way) with
      | 0 -> (1, pos + 1)
      | 1 -> (2, pos)
      | 2 -> (1, pos - 1)
      | 3 -> (0, pos)
      | _ -> failwith "invalid value" in
    if lines.(y).(x) = Wall then make_wall pos else lines.(y).(x) <- Wall in
  let rec loop pos =
    if pos < x * 2 - 1 then (
      if pos mod 2 = 1 then make_wall pos; loop (pos + 1)
    ) in
  loop 0

let main () =
  let _ = Random.init (int_of_float (Unix.time ())) in
  let filled_line = make_filled_line () in
  print_line filled_line;
  let rec loop cnt last_line =
    if cnt < y
      then (
        let lines = [|last_line; make_checked_line (); make_empty_line ()|] in
        make_maze (if cnt = 0 then Top else Normal) lines;
        print_line lines.(0);
        print_line lines.(1);
        loop (cnt + 1) lines.(2)
      )
      else print_line last_line in
  loop 0 (make_empty_line ());
  print_line filled_line

let _ = main ()

osiireさんからブログ経由でアドバイスを頂いたのを皮切りに、色々無駄な処理が気になってきたので再度修正した自己満足第三弾。Array.iter等を使うように、などなど。

type field = Space | Wall

let x = int_of_string (Sys.argv.(1))
let y = int_of_string (Sys.argv.(2))

let rec repeate f x i n =
  if i < n then repeate f (f i x) (i + 1) n else x

let make_line v = Array.make (x * 2 - 1) v

let make_empty_line () = make_line Space

let make_filled_line () = make_line Wall

let print_line line =
  print_string "■";
  Array.iter (
    fun a -> if a = Wall then print_string "■" else print_string "　"
  ) line;
  print_endline "■"

type mode = Top | Normal

let make_maze mode lines =
  let way = match mode with Top -> 4 | Normal -> 3 in
  let rec make_wall pos =
    let (y, x) =
      match (Random.int way) with
      | 0 -> (1, pos + 1)
      | 1 -> (2, pos)
      | 2 -> (1, pos - 1)
      | 3 -> (0, pos)
      | _ -> failwith "invalid value" in
    if lines.(y).(x) = Wall
      then make_wall pos
      else (
        lines.(1).(pos) <- Wall;
        lines.(y).(x) <- Wall
      ) in
  Array.iteri (fun i a -> if i mod 2 = 1 then make_wall i) lines.(0)

let main () =
  let _ = Random.init (int_of_float (Unix.time ())) in
  let draw_maze pos last_line =
    let lines = [|last_line; make_empty_line (); make_empty_line ()|] in
    make_maze (if pos = 0 then Top else Normal) lines;
    print_line lines.(0);
    print_line lines.(1);
    lines.(2) in
  let filled_line = make_filled_line () in
  print_line filled_line;
  print_line (repeate draw_maze (make_empty_line ()) 0 y);
  print_line filled_line

let _ = main ()

DouKaku?

必ず解ける迷路

Posted feedbacks - Flatten

Index

Feed

Other

Link

Pathtraq