Q22 百マス計算で最小のマスをたどると？

PHPのソース

<?php error_reporting(E_ALL);

//$YokoArr1 = array(3,5,0,8,1,4,2,6,7,9);
//$TateArr1 = array(4,8,1,7,0,6,9,2,5,3);
//Solve($YokoArr1,$TateArr1);

$YokoArr2 = array(8,6,8,9,3,4,1,7,6,1);
$TateArr2 = array(5,1,1,9,1,6,9,0,9,6);
Solve($YokoArr2,$TateArr2);

class JyoutaiDef
{
    public $CurrX;
    public $CurrY;
    public $Path;
    public $CostSum;
}

function Solve($pYokoArr,$pTateArr)
{
    define('UB', 9);
    $BanArr = array();
    for($Y = 0 ; $Y <= UB ; $Y++) $BanArr[] = array();

    for($X = 0 ; $X <= UB ; $X++){
        for($Y = 0 ; $Y <= UB ; $Y++){
            $BanArr[$X][$Y] = $pYokoArr[$X] + $pTateArr[$Y];
        }
    }

    //最小コストのメモ
    $MemoArr = array();
    for($Y = 0 ; $Y <= UB ; $Y++) $MemoArr[] = array();
    for($X = 0 ; $X <= UB ; $X++){
        for($Y = 0 ; $Y <= UB ; $Y++){
            $MemoArr[$X][$Y] = PHP_INT_MAX;
        }
    }

    $Stk = new SplStack();
    $WillPush = new JyoutaiDef();
    $WillPush->CurrX = 0;
    $WillPush->CurrY = 0;
    $WillPush->Path = strval($BanArr[0][0]);
    $WillPush->CostSum = $BanArr[0][0];
    $Stk->push($WillPush);

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

        //クリア判定
        if($Popped->CurrX == UB && $Popped->CurrY == UB){
            printf('解候補を発見。コスト=%d,経路=%s' , $Popped->CostSum , $Popped->Path);
            echo PHP_EOL;
            continue;
        }

        $HeniArr = array(array(0,-1),array(0,1),array(-1,0),array(1,0));
        foreach($HeniArr as $EachHeni){
            $NewX = $Popped->CurrX + $EachHeni[0];
            $NewY = $Popped->CurrY + $EachHeni[1];
            if($NewX < 0 || UB < $NewX) continue;
            if($NewY < 0 || UB < $NewY) continue;

            $WillPush = new JyoutaiDef();
            $WillPush->CurrX = $NewX;
            $WillPush->CurrY = $NewY;
            $WillPush->Path = $Popped->Path . sprintf(',%d' , $BanArr[$NewX][$NewY]);
            $WillPush->CostSum = $Popped->CostSum + $BanArr[$NewX][$NewY];

            //枝切り
            if($WillPush->CostSum > $MemoArr[$NewX][$NewY]) continue;
            $MemoArr[$NewX][$NewY] = $WillPush->CostSum;

            $Stk->push($WillPush);
        }
    }
}

実行結果

省略
解候補を発見。コスト=122,経路=13,9,7,9,10,4,5,2,2,10,2,7,10,1,7,6,1,10,7

解説

深さ優先探索で解いてます。