DouKaku? 5305 ivoryworks: 棒倒し法を用いています。 1024x1...(必ず解ける迷路)

Comment detail

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

Comment detail

Index

Feed

Other

Link

Pathtraq