提出 #65210376

---

ソースコード 拡げる

<?php
// ---------- 入力 ----------
function ints(){ $l = trim(fgets(STDIN)); return $l===''?[]:array_map('intval',explode(' ',$l)); }

[$N,$M] = ints();
$P=[];
for($i=0;$i<$M;$i++) $P[]=ints();

// 後で訪れることが確定しているマス
$willVisit=[];
foreach($P as $i=>$p)  $willVisit[$p[0]][$p[1]]=$i;

// ---------- パラメータ ----------
$maxWall   = 11;   // 置ける壁の上限
$beamWidth = 15;   // ビーム幅（大きくすると少し強いが計算量増）

// ---------- 移動／壁設置用ユーティリティ ----------
$DIR = [ [-1,0,'U'], [1,0,'D'], [0,-1,'L'], [0,1,'R'] ];

/* BFS (単移動＋スライド) で最短手順を求め，行動列を返す   */
/* 到達不可のときは null を返す                                 */
function bfs(array &$map,int $N,int $sy,int $sx,int $gy,int $gx): ?array{
    if($sy==$gy && $sx==$gx) return [];
    $dist=array_fill(0,$N,array_fill(0,$N,99));
    $prev=array_fill(0,$N,array_fill(0,$N,null));
    $act =array_fill(0,$N,array_fill(0,$N,''));
    $q=new SplQueue();
    $dist[$sy][$sx]=0;
    $q->enqueue([$sy,$sx]);
    $DIR=[[-1,0,'U'],[1,0,'D'],[0,-1,'L'],[0,1,'R']];
    while(!$q->isEmpty()){
        [$y,$x]=$q->dequeue();
        if($y==$gy && $x==$gx){
            $res=[];
            while(!($y==$sy&&$x==$sx)){
                $res[]=$act[$y][$x];
                [$y,$x]=explode(',',$prev[$y][$x]);
                $y=(int)$y; $x=(int)$x;
            }
            return array_reverse($res);
        }
        // 単ステップ
        foreach($DIR as [$dy,$dx,$c]){
            $ny=$y+$dy; $nx=$x+$dx;
            if(($map[$ny][$nx]??1)===0 && $dist[$ny][$nx]>$dist[$y][$x]+1){
                $dist[$ny][$nx]=$dist[$y][$x]+1;
                $q->enqueue([$ny,$nx]);
                $prev[$ny][$nx]="$y,$x";
                $act [$ny][$nx]="M $c";
            }
        }
        // スライド
        foreach($DIR as [$dy,$dx,$c]){
            $ny=$y; $nx=$x;
            while(isset($map[$ny+$dy][$nx+$dx]) && $map[$ny+$dy][$nx+$dx]==0){
                $ny+=$dy; $nx+=$dx;
            }
            if(($ny!=$y||$nx!=$x) && $dist[$ny][$nx]>$dist[$y][$x]+1){
                $dist[$ny][$nx]=$dist[$y][$x]+1;
                $q->enqueue([$ny,$nx]);
                $prev[$ny][$nx]="$y,$x";
                $act [$ny][$nx]="S $c";
            }
        }
    }
    return null;
}

// ---------- ビームサーチ用状態 ----------
class State{
    public int $y,$x,$cost,$wallCnt;
    public array $map,$acts;
    function __construct($y,$x,$map,$cost,$wallCnt,$acts){
        $this->y=$y; $this->x=$x; $this->map=$map;
        $this->cost=$cost; $this->wallCnt=$wallCnt; $this->acts=$acts;
    }
}

// ---------- 初期状態 ----------
$emptyMap = array_fill(0,$N,array_fill(0,$N,0));
$states   = [ new State($P[0][0],$P[0][1],$emptyMap,0,0,[]) ];

// ---------- 区間ごとのビーム展開 ----------
for($step=1;$step<$M;$step++){
    $gy=$P[$step][0]; $gx=$P[$step][1];
    $next=[];
    foreach($states as $st){
        // ① 壁を置かない
        $variants = [ [$st->map, [], 0] ];
        // ② 壁を 1 枚置く（4 方向） -------------
        if($st->wallCnt < $maxWall){
            $dirs = $DIR;                // 乱択
            shuffle($dirs);
            foreach($dirs as [$dy,$dx,$c]){
                $wy = $st->y+$dy; $wx=$st->x+$dx;
                if($wy<0||$wy>=$N||$wx<0||$wx>=$N)          continue; // outside
                if($st->map[$wy][$wx]!=0)                   continue; // already wall
                if(isset($willVisit[$wy][$wx]) && $willVisit[$wy][$wx]>=$step) continue; // 未来の訪問予定
                $newMap = $st->map;
                $newMap[$wy][$wx]=1;
                $variants[] = [ $newMap, ["A $c"], 1 ];
            }
        }
        // ---- 各バリアントを評価 ----
        foreach($variants as [$candMap,$addActs,$addWall]){
            $path = bfs($candMap,$N,$st->y,$st->x,$gy,$gx);
            if($path===null) continue;                      // 到達不可
            $acts = array_merge($st->acts,$addActs,$path);
            $cost = $st->cost + $addWall + count($path);
            $next[] = new State($gy,$gx,$candMap,$cost,$st->wallCnt+$addWall,$acts);
        }
    }
    if(!$next){  // 何らかの理由で空になったら壁を置かずに強制遷移
        foreach($states as $st){
            $path=bfs($st->map,$N,$st->y,$st->x,$gy,$gx);
            if($path===null) continue;
            $next[] = new State($gy,$gx,$st->map,
                                 $st->cost+count($path),
                                 $st->wallCnt,
                                 array_merge($st->acts,$path));
        }
    }
    // コスト昇順でビーム幅分に絞る
    usort($next, fn($a,$b)=>$a->cost<=>$b->cost);
    $states = array_slice($next,0,$beamWidth);
}

// ---------- 出力 ----------
$best=$states[0];
foreach($best->acts as $line) echo $line,"\n";
?>

提出情報

ジャッジ結果