AtCoderで水色を取得するため、コツコツと頑張っているところですが、再帰関数の実装でつまずいたので、備忘録程度に纏めておく。
今回解いた問題
ARC 031 B 埋め立て
10×10マスの中にいくつかの島があり、島と島の間に人工的な埋立地を１マス作ることで、大きな１つの島にできるか？といった問題である。
橙が島、青が海。赤枠がこの場合埋め立てると題意を満たす位置。
多重ループでガリガリ解いている方もいるのだが、ここは鍛錬と捉えて、学びたてホヤホヤの再帰関数を用いて解く。
前提
上記リンクから分かる通り、陸地は"o"、海は"x"と記述されている。
埋立地を作ることは"x"を"o"へ変えることに相当する。
方針
- 再帰関数を用いて深さ優先探索をしていく。
- 一度踏んだマスは履歴に残す。
- 探索できたマスの数 = 陸地の数 + 埋立地の数であれば、歩いて島全域を探索できたと見なす。（逆にこれを満たさないということは、１つの島しか歩かなかったということ）
- 探索は現在地から四方に動くのみ。
履歴の残し方は、stepped_fieldというすべての要素がFalseの10×10の配列を用意し、探索したマスはTrueに変えていく、といった感じ
コード
あとは方針通りに書いていくだけ。
変数名がなんか残念なのは経験不足だと思って大目に見てください（泣）
コード下部の二重for文で埋立地の位置を決めている。
import copy
init_field = list(list(input()) for _ in range(10))
un_stepped_field = list(list(False for _ in range(10)) for _ in range(10))
def count_continent(field):
continent_count = 0
for line in field:
continent_count += line.count("o")
return continent_count
def count_stepped_field(pre_counted_field):
stepped_count = 0
for line in pre_counted_field:
stepped_count += line.count(True)
return stepped_count
def search(y, x):
# マップ外やぞ。
if x < 0 or x >= 10 or y < 0 or y >= 10:
return
# 海歩いてるで。
if field[y][x] == "x":
return
# 前にここ来たで。
if stepped_field[y][x]:
return
stepped_field[y][x] = True
# ここで四方に探索
search(y+1, x)
search(y-1, x)
search(y, x+1)
search(y, x-1)
for i in range(10):
for j in range(10):
stepped_field = copy.deepcopy(un_stepped_field)
field = copy.deepcopy(init_field)
# 埋立地作るよ。
if field[j][i] == "x":
field[j][i] = "o"
# 探索開始なり。
search(j, i)
# 探索したマスの数が陸地の数と一致すれば題意を満たす。
if count_stepped_field(stepped_field) == count_continent(field):
print("YES")
exit()
print("NO")
苦労した点
二重for文の中のstepped_field = copy.deepcopy(un_stepped_field)だが、最初の実装では単にグローバル変数のun_step_fieldをserch関数内で用いていた。(変数名は直したが。)
それ故に、un_step_fieldは各ループで共有されるので、前のループの履歴が次のループに引き継がれていた。
結果として、未探索のマスなのに探索済みとしてカウントされていた。
それを解消すべく、各ループ毎にun_step_fieldをディープコピーすることで初期化を行っている。
あとは余り難しくなさそう（なお実装に時間はかかった模様。）