【AtCoder版！蟻本】ABC 088 D - Grid Repainting【幅優先探索】 - ebisukeプログラミング初心者脱出黙示録

f:id:ebisuke33:20210317142816p:plain
AtCoder版！蟻本の幅優先探索で類題としてあげられているABC088 DをPythonで解いていきます。

リンク

AtCoder Beginner Contest 088 D - Grid Repainting

問題文

縦 H マス, 横 W マスに広がるマス目があり, 各マスは白または黒で塗られている. 上から i 番目で左から j 番目のマスを (i,j) で表す. すぬけ君は, このマス目を使って次のようなゲームをしたい. ゲームの開始時点ではマス (1,1) にゲームキャラクター「けぬす君」がいる. プレイヤーはけぬす君を上下左右の 4 方向のいずれかに 1 マスだけ動かすことを繰り返す. けぬす君が白いマスだけを通って (H,W) にたどり着けばゲームクリアとなる.
ゲームを開始する前に, すぬけ君はいくつかの白いマス目の色を黒に変えることができる. ただし, マス (1,1) と (H,W) の色を変えることはできず, ゲームを開始するまでにすべての色の変更を行わなければならない.
ゲームをクリアしたとき, ゲームの開始前にマスの色を変えた回数がすぬけ君のスコアとなる. そのとき, すぬけ君が取る可能性のある最大のスコアを求めなさい.ただし, すぬけ君がどのようにマス目の色を変えてもけぬす君が (H,W) にたどり着くことが出来ない場合、−1 と出力しなさい.
ただし, 各マスの色の情報は文字 si,j として与えられる. マス (i,j) が最初白で塗られている場合 si,j は . であり, マス (i,j) が最初黒で塗られている場合 si,j は # である.

制約

・H は 2 以上 50 以下の整数
・W は 2 以上 50 以下の整数
・si,j は . または # (1≤i≤H,1≤j≤W)
・s1,1, sH,W は . である

解答例

from collections import deque

# 入力
h, w = map(int,input().split())

maze = [] # 迷路の文字配列
for _ in range(h):
    maze.append(input())

# 各座標への最短距離の配列（INFで初期化）
INF = int(1e9)
D = [[INF] * w for i in range(h)]

# 4方向の移動ベクトル
dx = [1,0,-1,0]
dy = [0,1,0,-1]

# スタート地点
sy = 0
sx = 0
# ゴール地点
gy = h-1
gx = w-1


# スタートからゴールへの最短距離を求める
def bfs():
    que = deque()
    que.append([sy,sx]) # スタート地点をキューに入れる
    D[sy][sx] = 0 # スタート地点の距離を0とする

    # キューが空になるまで探索
    while len(que) != 0:
        p = que.popleft() # 先入れのキューの要素を取り出す
        if p[0] == gy and p[1] == gx: # ゴールなら探索終了
            break
        for i in range(4): # pから4方向に移動 移動後の点は(nx,ny)
            ny = p[0] + dy[i]
            nx = p[1] + dx[i]
            # 移動可能か、訪れたことがあるかの判定
            if 0 <= nx < w and 0 <= ny < h and maze[ny][nx] != "#" and D[ny][nx] == INF:
                # 移動可能ならキューに入れて、その点の距離をpからの距離+1で確定する
                que.append([ny,nx])
                D[ny][nx] = D[p[0]][p[1]] + 1
    return D[gy][gx]

# 最初黒色のマスの数
def black_count():
    black_num = 0 # 黒色のマス目の数
    for i in range(h):
        for j in range(w):
            if maze[i][j] == "#":
                black_num += 1
    return black_num

tmp = bfs()
num = black_count()
if tmp == INF:
    print(-1)
else:
    res = h * w - tmp - num - 1
    print(res)

解説

縦 H マス, 横 W マスのマス目が白色か黒色で塗られていて、マス (1,1) からスタートし白色のマスだけを通ってマス (H,W)を目指します。
スタート前に白色のマスを黒色に変えることができ、塗り替えたマス目の数に応じて得点がもらえます。
このルールで最大何点をとることができるか、あるいはゴールにたどり着けないか答える問題です。

初期状態のまま幅優先探索BFSでスタートからゴールへの最短経路を求めます。
この最短経路以外のマス目は黒に塗り替えても通らないで済むので、これを元に黒に塗り替える最大のマス目を解答する方針です。

幅優先探索は特に工夫しておらず、問題文から求まるスタート地点とゴール地点を代入して最短経路を求めます。
基本的な幅優先探索は次の記事で記載しました。
ebisuke33.hatenablog.com

次に初期状態の黒色のマス目を数えます。
black_count関数を作り、単純に全探索して黒色のマス目を数えます。

このふたつが求まれば、黒色に塗り替えることのできるマス目の最大値resは、H×Wのマス目から最短経路ともともと黒色のマス目の数＋1を引いた値になります。
もし、スタートからゴールにたどり着けないときはBFSでINFが返ってくるので、-1を出力し、それ以外のときはresを出力すればOKです。

AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com

リンク