DouKaku?

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

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

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

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

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

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

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


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

棒倒し法で何も工夫していない上に、なでしこなので速度は遅め・・・。
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)