必ず解ける迷路 in PHP DouKaku?

必ず解ける迷路

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

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

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

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

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

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

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


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

post comment

Posted feedbacks - PHP

棒倒し法を用いています。
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';
}
?>

DouKaku?

必ず解ける迷路

Posted feedbacks - PHP

Index

Feed

Other

Link

Pathtraq