2026.08.14

記事内に商品プロモーションを含む場合があります

【アルゴリズム】ロボットの向きを状態に持つ「拡張BFS」をマスターしよう【Python】

Aru

この記事では、グリッド（格子状のマス目）上をロボットが移動する問題について解説します。一見するとシンプルな経路探索問題に見えますが、一般的な迷路と違って「ロボットは回転と前進」しかできない、という点に特徴があります。

このような問題は、ロボットの「向き」を状態に含めて探索する「拡張BFS（状態空間BFS）」を用います。

Contents

問題の概要
解法：ロボットの向きを状態に持つ「拡張BFS」
- 状態の定義
- 遷移（次の状態への移動）
Pythonによる実装例
コードの詳しい解説
まとめ

問題の概要

まずは、今回挑戦する問題の概要です。

問題文

$N \times M$ の迷路があり、通路 . と壁 # で構成されています。ロボットは最初、左上 $(1, 1)$ にいて、右（東）を向いています。目標は、右下 $(N, M)$ に到達することです。

ロボットができる行動は以下の3つです（それぞれ操作回数 1）：

右回転（時計回りに90度向きを変える：右 $\to$ 下 $\to$ 左 $\to$ 上 $\to$ 右）
左回転（反時計回りに90度向きを変える：右 $\to$ 上 $\to$ 左 $\to$ 下 $\to$ 右）
前方に1マス進む（壁や迷路の外には進めない）

最小の操作回数を求めてください。到達できない場合は -1 を出力します。

制約

$2 \le N, M \le 1000$
スタート $(1, 1)$ とゴール $(N, M)$ は必ず通路 .

入力形式

N M
1行目（迷路の最上行＝問題上の行 N）
2行目
:
N行目（迷路の最下行＝問題上の行 1）

サンプル１

入力

2 2
..
..

出力

左上 $(1, 1)$ から右下 $(2, 2)$ を目指します。初期向きは「右」です。

右に 1 マス進んで $(1, 2)$ へ（1操作）
右回転して下を向く（2操作）
下に 1 マス進んで $(2, 2)$ に到達（3操作）

合計 3 操作で到達できます。

サンプル２

入力

2 2
..
.#

出力

右隣の $(1, 2)$ が壁 # になっています。初期向きは右ですが、目の前が壁なのでそのまま進むことはできません。

右回転して下を向く（1操作）
下に 1 マス進んで $(2, 1)$ へ（2操作）
左回転して右を向く（3操作）
右に 1 マス進んで $(2, 2)$ に到達（4操作）

合計 4 操作で、壁を上手に避けてゴールできます

解法：ロボットの向きを状態に持つ「拡張BFS」

迷路の最短経路問題といえば幅優先探索（BFS）が定番ですが、今回は「現在地 $(r, c)$」に加えて、ロボットがどちらを向いているかという「向き（dir）」の情報も必要になります。

なぜなら、同じマスにいても「右を向いている状態」と「下を向いている状態」では、次に進めるマスの選択肢や、必要な回転数が異なるからです。

このように、位置情報だけでなく追加のパラメータ（状態）を持たせて探索することを、競プロでは拡張BFS（または状態空間BFS）と呼びます。

状態の定義

最小操作回数（距離）を記録する配列 dist を、以下のように3次元で用意します。$$\text{dist}[r][c][dir] = \text{座標 }(r, c) \text{ に、向き } dir \text{ で到達する最小操作回数}$$

向き $dir$ は、以下のように数字で管理すると回転の処理がとても楽になります。

0 : 上方向（行 $-1$）
1 : 右方向（列 $+1$）
2 : 下方向（行 $+1$）
3 : 左方向（列 $-1$）

こうすると、右回転（時計回り）は (dir + 1) % 4、左回転（反時計回り）は (dir - 1) % 4 で一発で表現できます。

💡 Pythonの嬉しい仕様 Pythonの % 4 演算は、負の数に対しても自動的に正しく剰余を計算してくれます（例: (-1) % 4 は 3 になる）。そのため、左回転も (dir - 1) % 4 とそのまま書くだけでスマートに処理できます。

遷移（次の状態への移動）

現在の状態が $(r, c, dir)$ のとき、次の2つの遷移が考えられます。

回転する（右回転・左回転）
- 向きを $nd$ に変える（場所はそのまま）。
- コストは $+1$。
- dist[r][c][nd] = dist[r][c][dir] + 1
前方に1マス進む
- 現在の向き $dir$ にしたがって、隣のマス $(nr, nc)$ に進む（向きはそのまま）。
- 進んだ先が壁でなく、迷路の範囲内である必要があります。
- コストは $+1$。
- dist[nr][nc][dir] = dist[r][c][dir] + 1

これをキュー（deque）を使って順番に探索していけば、ゴールの座標（プログラム上の $(H-1, W-1)$）におけるすべての向きの最小値が答えになります。

Pythonによる実装例

それでは、実際のPythonコードを見てみましょう。問題文の1始まりの座標 $(1, 1) \sim (N, M)$ を、プログラム上では扱いやすい0始まりのインデックス $(0, 0) \sim (H-1, W-1)$ に直して実装しています。

from collections import deque

# H: 行数 (N), W: 列数 (M)
H, W = map(int, input().split())
s = [input() for _ in range(H)]

# スタートやゴールが最初から壁の場合は到達不可能
if s[0][0] == '#': 
    print(-1)
    exit()

if s[H-1][W-1] == '#':
    print(-1)
    exit()

# 非常に大きい値（初期値）
inf = 10**18

# dist[r][c][dir]: 座標 (r, c) に 向き dir で到達するときの最小操作回数
# dir の定義 -> 0: 上, 1: 右, 2: 下, 3: 左
dist = [[[inf, inf, inf, inf] for _ in range(W)] for _ in range(H)]

# スタート地点 (0, 0) に、右(1)を向いて初期化（操作回数 0）
dist[0][0][1] = 0
q = deque()
q.append((0, 0, 1))

# 各向きに対応する移動量 (上, 右, 下, 左)
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]

while len(q) != 0:
    r, c, direction = q.popleft()

    # --- 1. 方向回転の遷移 ---
    # i = -1 (左回転), i = 1 (右回転) を試す
    for i in [-1, 1]:
        nd = (direction + i) % 4
        if dist[r][c][nd] == inf:
            dist[r][c][nd] = dist[r][c][direction] + 1
            q.append((r, c, nd))

    # --- 2. 前方に進む遷移 ---
    nr = r + dr[direction]
    nc = c + dc[direction]
    
    # 迷路の外に出る場合は進めない
    if nr < 0 or nr >= H or nc < 0 or nc >= W:
        continue
    # 壁がある場合は進めない
    if s[nr][nc] == '#': 
        continue
    
    # まだ訪れていないなら更新
    if dist[nr][nc][direction] == inf:
        dist[nr][nc][direction] = dist[r][c][direction] + 1
        q.append((nr, nc, direction))

# ゴール地点 (H-1, W-1) での、すべての向きの中の最小値を取得
ans = min(dist[H-1][W-1])

if ans == inf:
    print(-1)
else:
    print(ans)

コードの詳しい解説

コードの重要なポイントをいくつかピックアップして解説します

① 方向転換のループ処理

for i in [-1, 1]:
    nd = (direction + i) % 4

単純なループで書く際、range(-1, +2)（つまり -1, 0, 1）としてしまうと、0（回転せずその場に留まる遷移）の処理が含まれてしまいます。その場に留まる遷移はコストが余分にかかるだけで、最短経路の更新には寄与しないため、実質的に [-1, 1]（左回転と右回転）だけを試せば十分です。

前述の通り、Pythonの % 4 演算の仕様を活かすことで、回転後の向きをとてもスマートに1行で表現できています。

②移動

ロボットは、前進しか行うことができないので、現在向いている方向dirへの移動だけをチェックします。ここも通常の経路探索とは異なります。

③ 計算量

状態数： $N \times M \times 4$ （約 $1000 \times 1000 \times 4 = 4 \times 10^6$ 状態）
遷移数：各状態から「右回転」「左回転」「前進」の最大3通り。
計算量：全体の計算量は $\mathcal{O}(NM)$ となります。

$N, M \le 1000$ なので、Pythonでも 1秒以内に余裕で実行できます。