最短経路(幅優先探索)

問題

$ H \times W $ の長方形状のグリッドがあり、各マスは白か黒に塗られています。

上から $ i $ 番目、左から $ j $ 番目のマスを $ (i, j) $ と表すことにします。

左上のマス $ (0,0) $ と右下のマス $ (H -1, W - 1) $ は白色です。

このグリッドの入力データは、$ H $ 個の長さ $ W $ の文字列 $ S_0, S_1, …, S_{H-1} $ として与えられます。

文字列 $ S_i $ の $ j $ 番目の文字は、マス $ (i,j) $ が白色の時は ‘,’(カンマ) であり、黒色の時は ‘#’(シャープ) です。

マス $ (0,0) $ からマス $ (H-1, W-1) $ まで白色マスのみを辿って行くことができる状態を保ちつつ、白色マスを黒色マスに塗り替える場合、黒く塗れるマスの最大個数はいくつになるでしょうか。

解法・ソースコード

この問題は、マス(0, 0)からマス(H - 1, W -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
from queue import Queue
#--------- 入力例 -----------
s = ['.....#',
'####..',
'......',
'#.####',
'......']
#----------------------------
h = len(s) # グリッドの高さ
w = len(s[0]) # グリッドの横幅

# マス(x,y)を表すペア
que = Queue()
# dist[x,y]は、マス(x,y)への最短経路長
dist = [[-1] * w for _ in range(h)]

# 幅優先探索の初期条件
que.put((0, 0)) # スタート位置
dist[0][0] = 0

# 幅優先探索
while que.empty() == False:
# キューから要素を取り出す
qx, qy = que.get()

# 上下左右への移動を試す
for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
x, y = qx + dx, qy + dy
# 配列外の参照の場合
if x < 0 or x >= h or y < 0 or y >= w:
continue
# 白マスの場合 かつ マス(x, y)が未探索の場合
if s[x][y] == '.' and dist[x][y] < 0:
# マス(x, y)をキューに追加して、最短経路長を更新
que.put((x, y))
dist[x][y] = dist[qx][qy] + 1

# 白マスの数をカウント
cnt_white = sum(line.count('.') for line in s)

print('解:', cnt_white - dist[h - 1][w - 1] - 1)

[実行結果]

解: 4

次のように4マスを黒く塗り替えることができ、右上から左下への最短経路はそのまま残すことができます。

(変更前)  (変更後)
.....#   .....#
####..   ####.#
...... ➡ #....#
#.####   #.####
......   #.....