必ず解ける迷路 in Perl DouKaku?

必ず解ける迷路

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

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

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

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

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

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

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


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

post comment

Posted feedbacks - Perl

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);
}

DouKaku?

必ず解ける迷路

Posted feedbacks - Perl

Index

Feed

Other

Link

Pathtraq