幅優先探索（Depth First Search）②

問題

$ H \times W $ のマス目で表される迷路があります。

迷路の情報は文字列のリストとして表され、各文字は壁(‘#’) または 通過できる場所(‘.’)となります。

スタート座標からゴール座標までの最短移動回数を求めて下さい。

[制約]
🔹$ 1 \leqq H \leqq 100000 $
🔹$ 1 \leqq W \leqq 100000 $

解き方・ソースコード

前回記事と同様に幅優先探索を使ってこの問題を解いていきます。

前回記事ではqueueを使いましたが、今回はリストで代用します。

また、キューに格納したマス情報は削除せずに、追加した順番にキューの最後までチェックします。

上下左右にマスに移動する処理は関数化（push関数）し、壁の場合はパスし、通過できるマスの場合はコストを１つ増やして、そのマスをキューに追加しています。

cost配列（移動回数を管理）のインデックスは、0からではなく1から始まっています。

このため、push関数で引数に渡す座標値を $sx - 1, sy - 1, gx - 1, gy - 1$ にする必要があります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#-------- 入力例１ ---------
H, W = 7, 8     # 高さ、横幅
sx, sy = 2, 2   # スタート地点の x,y 座標
gx, gy = 4, 5   # ゴール地点の x,y 座標
# 迷路
S = [
  '########',
  '#......#',
  '#.######',
  '#..#...#',
  '#..##..#',
  '##.....#',
  '########'
]
#-------- 入力例２ ---------
H, W = 5, 8     # 高さ、横幅
sx, sy = 2, 2   # スタート地点の x,y 座標
gx, gy = 2, 4   # ゴール地点の x,y 座標
# 迷路
S = [
  '########',
  '#.#....#',
  '#.###..#',
  '#......#',
  '########'
]

#---------------------------
# マスごとの移動回数
cost = [[float('inf')] * W for _ in range(H)]

q = [] # queue は list で代用

# マスに移動する部分を関数化
def push(x, y, c):
    if S[x][y] == '#':  # 壁なので移動できない
        return
    if cost[x][y] <= c: # より少ない移動回数で移動済み（設定済み）
        return
    cost[x][y] = c
    q.append((x, y))

# 幅優先探索
push(sx - 1, sy - 1, 0)
for x, y in q:
    # コストを１つ増やす
    c2 = cost[x][y] + 1
    # 上下左右をチェック
    push(x - 1, y, c2)
    push(x, y - 1, c2)
    push(x + 1, y, c2)
    push(x, y + 1, c2)

print('解：', cost[gx - 1][gy - 1])

[実行結果（入力例１）]

解： 11

[実行結果（入力例２）]

解： 10

迷路に対する最短移動回数を求めることができました。