【AtCoder版！蟻本】ARC 031 B - 埋め立て【深さ優先探索】

AtCoder版！蟻本の深さ優先探索で類題としてあげられているARC031 BをPythonで解いていきます。
再帰関数を使用して解いています。

リンク

atcoder.jp

AtCoder Regular Contest 031 B - 埋め立て

問題文

とある所に島国がありました。島国にはいくつかの島があります。このたび、この島国で埋め立て計画が立案されたのですが、どこを埋め立てるか決まっていません。できることなら埋め立てによって島を繋いで、1 つの島にしてしまいたいのですが、たくさん埋め立てるわけにもいきません。
10 マス × 10 マスのこの島国の地図が与えられるので、1 マスを埋め立てた時に 1 つの島にできるか判定してください。ただし、地図で陸地を表すマスが上下左右につながっている領域のことを島と呼びます。

制約

・各行は 10 文字からなり、o は陸地を、x は海を表す。
・少なくとも 1 マスは陸地があることが保証される。
・少なくとも 1 マスは海があることが保証される

解答例

import copy

Map = [] # 10*10マスの地図
for _ in range(10):
    Map.append(list(input()))

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

# 現在地に隣接する陸地を海に置き換える
def dfs(x, y):
    # 今いるところをxに置き換える
    if New_map[x][y] == "o":
        New_map[x][y] = "x"
    for k in range(4): # x方向にdx y方向にdy 移動した場所を(nx, ny)とする
        nx = x + dx[k]
        ny = y + dy[k]
        # nxとnyがMap内で陸地か判別
        if 0 <= nx < 10 and 0 <= ny < 10 and New_map[nx][ny] == "o":
            dfs(nx,ny)
    return

for i in range(10):
    for j in range(10):
        if Map[i][j] == "x":
            New_map = copy.deepcopy(Map)
            dfs(i,j)
        else:
            continue
        
        flag = True
        for a in range(10):
            for b in range(10):
                if New_map[a][b] == "o":
                    flag = False
        if flag:
            print("YES")
            exit()
else:
    print("NO")

解説

10×10マスの島国の地図があり、海を1マスだけ陸に変えたときに1つの島になるか判定する問題です。

初期状態のマップのうち各マスを全探索し、海であればその地点をDFSに渡します。

DFSでは渡された地点から縦横4マスに陸地があれば海に置き換えていきます。
スタート地点から隣接した陸はすべて海になります。
この後に海に置き換えた地図に陸地がないか全探索します。
これで陸地がないことを確認できたらYESを出力し、ループが抜けてしまったらNOを出力すればOKです。

ループごとにdeepcopyを使ってNew_mapを初期化しないと引き継ぎたくないのに引き継がれてしまい苦労しました。

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

リンク