倉庫の通路でゴールまでの最短の歩数

迷路と盤面
問題 14
ふつう
目安 31 分

棚と通路の地図から、スタートからゴールまで何歩で行けるかを求める。幅優先探索で、近いマスから順に距離を決めていく練習です。

本番の試験は PC で受けることが多いので、PC での練習をすすめます。スマホでも、読んで、書いて、採点するところまで動きます。

入力は標準入力から読み、答えは標準出力に書きます。1 テストあたり 2 秒までです。

問題

ある倉庫の床の地図が、H 行 W 列のマス目で与えられます。各マスは次のどれかの文字で表されます。

. は通路で、通れます
# は棚で、通れません
S はスタートの位置で、通れます
G はゴールの位置で、通れます

作業員は 1 歩で、上下左右のとなりのマスへ 1 つだけ動けます。ななめには動けず、地図の外にも出られません。スタートからゴールまで行くのに必要な最少の歩数を出力してください。ゴールまで行けないときは -1 を出力してください。

入力の形式

H W
s_1
s_2
...
s_H

1 行目に行の数 H と列の数 W が半角の空白 1 つで区切られて並びます。続く H 行は地図で、i 行目の s_i は長さ W の文字列です。

出力の形式

最少の歩数を 1 行で出力します。行けないときは -1 を出力します。

制約

H と W は、どちらも 1 以上 500 以下です。H × W は 2 以上です
地図は . # S G の 4 種類の文字だけでできています
S と G は、地図の中にちょうど 1 つずつあります

入力と出力の例

例 1

左上の S から、右下の G へ向かいます。下へ 2 歩、右へ 3 歩の 5 歩で着きます。これより少ない歩数の道はありません。

入力

3 4
S.#.
.#..
...G

出力

例 2

真ん中の列が全部棚なので、S のある左側から G のある右側へは行けません。

入力

2 3
S#G
.#.

出力

-1

ヒント

まだ開いていません

付箋は 3 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3答えに近い

全部のテストに通ると、解答と考え方が開きます。

先にヒントを試すと、自分で解けた手応えが残ります。どうしても詰まったときは、ここから開けます。

解答

S から幅優先探索をします。歩数の表を -1 で埋め、S を 0 歩にして待ち行列に入れます。列の前からマスを取り出し、上下左右のとなりのうち、地図の中にあり、棚ではなく、まだ歩数が決まっていないマスに「今のマスの歩数 + 1」を書いて、列の後ろに入れます。G の歩数が答えです。最後まで G に来なければ、表には -1 が残っているので、それをそのまま出力します。各マスは 1 回だけ列に入るので、全部で O(H × W) です。

Python

import sys
from collections import deque

data = sys.stdin.read().split()
h, w = int(data[0]), int(data[1])
grid = data[2:2 + h]

for r in range(h):
    for c in range(w):
        if grid[r][c] == "S":
            start = (r, c)
        elif grid[r][c] == "G":
            goal = (r, c)

dist = [[-1] * w for _ in range(h)]
dist[start[0]][start[1]] = 0
queue = deque([start])
while queue:
    r, c = queue.popleft()
    if (r, c) == goal:
        break
    for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
        if 0 <= nr < h and 0 <= nc < w and grid[nr][nc] != "#" and dist[nr][nc] == -1:
            dist[nr][nc] = dist[r][c] + 1
            queue.append((nr, nc))

print(dist[goal[0]][goal[1]])

JavaScript

const lines = require("fs").readFileSync(0, "utf8").split(/\s+/).filter(Boolean);
const [h, w] = lines.slice(0, 2).map(Number);
const grid = lines.slice(2, 2 + h);

let start = null;
let goal = null;
for (let r = 0; r < h; r++) {
  for (let c = 0; c < w; c++) {
    if (grid[r][c] === "S") start = [r, c];
    else if (grid[r][c] === "G") goal = [r, c];
  }
}

const dist = Array.from({ length: h }, () => new Array(w).fill(-1));
dist[start[0]][start[1]] = 0;
const queue = [start];
let head = 0;
while (head < queue.length) {
  const [r, c] = queue[head++];
  if (r === goal[0] && c === goal[1]) break;
  for (const [nr, nc] of [[r - 1, c], [r + 1, c], [r, c - 1], [r, c + 1]]) {
    if (nr >= 0 && nr < h && nc >= 0 && nc < w && grid[nr][nc] !== "#" && dist[nr][nc] === -1) {
      dist[nr][nc] = dist[r][c] + 1;
      queue.push([nr, nc]);
    }
  }
}

console.log(dist[goal[0]][goal[1]]);

計算量

時間は O(H × W) です。各マスは 1 回だけ待ち行列に入り、取り出したときにとなりの 4 マスを調べるだけだからです。H と W が 500 なら 25 万マスで、十分に間に合います。

遅い解き方の例は、歩数の表を「とても大きな数」で埋め、全部のマスを上から順に見て「となりの歩数 + 1 のほうが小さければ書き換える」を、どこも書き換わらなくなるまで繰り返すものです。答えは合いますが、道が左右に折り返す迷路では、左へ戻る道の歩数が 1 回の見直しで 1 マスずつしか伝わりません。見直しが何万回も要り、1 回ごとに 25 万マスを見るので、数十億回の計算になって時間切れになります。

よくある間違い

待ち行列に入れるときではなく、取り出したときに「来た」と印を付ける。同じマスが何度も列に入り、遅くなったり、メモリが足りなくなったりします
Python で list の pop(0) を使って前から取り出す。1 回ごとに全体をずらすので O(列の長さ) かかり、大きな迷路で遅くなります。deque の popleft() を使います
深さ優先探索で最初に見つけた道の歩数を答えにする。深さ優先では、最初に着いた道が最短とは限りません
行と列を取り違える。入力は H 行 W 列で、grid[r][c] の r が行 (0 以上 H 未満)、c が列 (0 以上 W 未満) です
ゴールに行けないときに -1 を出さず、何も出力しないか、大きな数を出してしまう

解答を動かした版 Python 3.12.14Node.js 22.23.4確認日 2026/10/31

main.py

import sys

data = sys.stdin.read().split()
h, w = int(data[0]), int(data[1])
grid = data[2:2 + h]

# ここから書く
# grid[r][c] が r 行目 c 列目 (どちらも 0 から数える) の文字です

入力

3 4
S.#.
.#..
...G

出力

「実行する」を押すと、ここに出力が出ます

できているか「提出して採点」を押すと、隠れたテストを全部走らせて、通ったかをここに出します