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 - PostScript

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

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

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

# 昔、256 bytes のコードで連続紙に迷路を延々
# 出力しつづけるプログラムがあったなぁ....
 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
%!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 にしようかと思いましたが、あまり小さくならないので、そのままつっこみます。

 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
%!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

Index

Feed

Other

Link

Pathtraq

loading...
Creative Commons License このサイトの内容は、 クリエイティブ・コモンズ・ライセンスの下でライセンスされています。 [詳細]