問題
$ 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 | from queue import Queue |
[実行結果]
解: 4
次のように4マスを黒く塗り替えることができ、右上から左下への最短経路はそのまま残すことができます。
(変更前) (変更後) .....# .....# ####.. ####.# ...... ➡ #....# #.#### #.#### ...... #.....