問題: 迷路の最短経路 (PHP)

迷路の最短経路 (PHP)

問題

1行目に迷路の行数 h と列数 w、続く h 行に迷路を入力として受け取ります。'.' は通路、'#' は壁です。左上から右下までの最短手数を幅優先探索で求めて表示してください。たどり着けない場合はその旨を表示します。

入力例

5 5
.#...
.#.#.
...#.
##.#.
...#.

出力例

最短手数: 12

参照コード

コピーはできません。自分でタイピングしてください。

<?php
list($h, $w) = array_map('intval', explode(" ", trim(fgets(STDIN))));
$grid = [];
for ($i = 0; $i < $h; $i++) {
    $grid[] = trim(fgets(STDIN));
}
$dist = array_fill(0, $h, array_fill(0, $w, -1));
$dist[0][0] = 0;
$queue = [[0, 0]];
$dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
while (count($queue) > 0) {
    [$y, $x] = array_shift($queue);
    foreach ($dirs as [$dy, $dx]) {
        $ny = $y + $dy;
        $nx = $x + $dx;
        if ($ny < 0 || $ny >= $h || $nx < 0 || $nx >= $w) {
            continue;
        }
        if ($grid[$ny][$nx] == "#" || $dist[$ny][$nx] != -1) {
            continue;
        }
        $dist[$ny][$nx] = $dist[$y][$x] + 1;
        $queue[] = [$ny, $nx];
    }
}
if ($dist[$h - 1][$w - 1] == -1) {
    echo "ゴールにたどり着けません\n";
} else {
    echo "最短手数: " . $dist[$h - 1][$w - 1] . "\n";
}
?>

迷路の最短経路 (PHP)

問題

入力例

出力例

参照コード

入力エリア