Q18 非常階段での脱出パターン

PHPのソース

<?php
Solve( 3);
Solve(16);

function Solve($pDansuu)
{
    $HaitiArr = ExecDFS($pDansuu);

    $Answer = 0;
    foreach($HaitiArr as $EachHaiti){
        $Answer += DeriveCnt($EachHaiti,$pDansuu);
    }
    echo "{$pDansuu}段だと{$Answer}回" . PHP_EOL;
}

class JyoutaiDef
{
    public $CurrVal;
    public $CurrSet;
}

//深さ優先探索で配置を列挙
function ExecDFS($pDansuu)
{
    $WillReturn = array();

    $Stk = new SplStack();
    $WillPush = new JyoutaiDef();
    $WillPush->CurrVal = 1;
    $WillPush->CurrSet = array();
    $Stk->push($WillPush);

    while($Stk->isEmpty() == false){
        $Popped = $Stk->pop();

        for($I = $Popped->CurrVal ; $I <= $pDansuu ; $I++){
            $WillPush = clone $Popped;
            $WillPush->CurrVal = $I + 1;
            $WillPush->CurrSet[] = $I;
            $Stk->push($WillPush);
            $WillReturn[] = $WillPush->CurrSet;
        }
    }
    return $WillReturn;
}

//配置を引数として、脱出までの回数を返す
function DeriveCnt($pHaiti , $pDansuu)
{
    $PrevArr = $pHaiti;
    $Answer = 0;
    while(count($PrevArr) > 0){
        $CurrArr = array();
        foreach($PrevArr as $EachVal){
            if ($EachVal == $pDansuu) continue;
            $NextVal = $EachVal + 1;
            if(in_array($NextVal,$PrevArr)) $CurrArr[] = $EachVal;
            else $CurrArr[] = $NextVal;
        }
        $Answer++;
        $PrevArr = $CurrArr;
    }
    return $Answer;
}

実行結果

3段だと21回
16段だと1149133回

解説

深さ優先探索で配置を列挙してから、
シュミレーションしてます。