『必ず解ける迷路』投稿

2008/1/14 00:00

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

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

迷路生成のアルゴリズムはここを参考にさせて頂きました。　迷路のアルゴリズムなんてこんな機会が無ければ調べたり考えたりする事ないので楽しかったです。

以下投稿したコード。選択した言語はPHP。「棒倒し法」と呼ばれるアルゴリズムを採用しています。暇を見つけて「穴掘り法」や「壁延ばし法」などでも組んで見たいと思っています。

<?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’;  
}  
?>