Loading...

プレビュー

全38ステップ中12ステップのみ表示

ログインして全て見る

迷路脱出

中級

Maze Escape

BFSを使用して2Dグリッド迷路で最短経路を見つける問題

📊 計算量

区分	計算量
平均	O(N×M)
最悪	O(N×M)
空間	O(N×M)

🏷️ Tags

BFSグラフ最短経路2Dグリッド

📋 問題

配達ロボットの最短経路

物流倉庫で配達ロボットが商品を配送します。倉庫はN×Mグリッドで構成され、一部のセルには棚（障害物）があります。ロボットは上下左右の4方向にのみ移動できます。出発地(S)から到着地(E)までの最小移動回数を求めてください。

1/38

Loading...

🤖配達ロボット出動!

倉庫でS（開始）からE（終了）までの最短経路を見つけよう!

🔒

配達ロボットの最短経路

問題説明

物流倉庫で配達ロボットが商品を配送します。倉庫はN×Mグリッドで構成され、一部のセルには棚（障害物）があります。ロボットは上下左右の4方向にのみ移動できます。出発地(S)から到着地(E)までの最小移動回数を求めてください。

入力

1行目：倉庫サイズ N M (1 ≤ N, M ≤ 100) 次のN行：倉庫構造 '.' : 空のセル（通過可能） '#' : 棚（通過不可） 'S' : 開始点 'E' : 終了点

出力

出発地から到着地までの最小移動回数（到達不可能な場合は-1）

制約条件

•1 ≤ N, M ≤ 100
•開始点と終了点は常に存在
•開始点と終了点は常に異なる

例

例 1

入力

5 5
S . . # .
. # . # .
. # . . .
. . # # .
# . . . E

出力

説明

→→↓↓↓→→↓ または ↓↓↓↓→→→↓ 経路で8マス移動

迷路脱出 | AlgoNote