AtCoder Regular Contest 031 B – 埋め立て

Share

AtCoder上にある問題のうち、AtCoder Problemsでdiff 800以上と判定されているものを順番に解いていく企画。
基本的な考え方は全てコード中のコメントに入れてあるので、参照のこと。

出典:
AtCoder Regular Contest 031 B – 埋め立て

力技で解けばいい。Union_Findなどで探索を効率化できるような気もするが、面倒くさそうなのでここではやらない。

# AtCoder Regular Contest 031 B - 埋め立て
# https://atcoder.jp/contests/arc031/tasks/arc031_2
# グリッド 連結 BFS DFS

# ひとマスずつそこを埋め立てて連結になるかどうかを
# 確認していく。

def main():
field = [[c for c in input()] for _ in range(10)]

# 与えられた地図を元に、陸地が全てつながっているか
# どうかを確認する関数を作成しておく。
def land_connectedp(field):
moves = ((-1, 0), (1, 0), (0, -1), (0, 1))
connection = 0
visited = [[False] * 10 for _ in range(10)]

# 探索開始地点をすべての場所から試す
for sx in range(10):
for sy in range(10):
# 訪問済み、もしくは海ならスキップする
if visited[sy][sx] or field[sy][sx] == 'x':
continue

# 陸地が見つかったら、連結成分数のカウントを増やしつつ、
# 繋がっている陸地を全て訪問済みにする。
connection += 1
queue = [(sx, sy)]
visited[sy][sx] = True
while queue:
x, y = queue.pop()
for dx, dy in moves:
tx, ty = x + dx, y + dy
if not (0 <= tx < 10 and 0 <= ty < 10):
continue
if visited[ty][tx] == False and field[ty][tx] == 'o':
visited[ty][tx] = True
queue.append((tx, ty))

# 連結成分数が 1 なら、陸地は全て繋がっている。
return connection == 1

# 最初から繋がっていれば YES
if land_connectedp(field):
print('YES')
return

# 埋立地の場所を全探索する。
for fx in range(10):
for fy in range(10):
# 陸ならスキップ。
if field[fy][fx] == 'o':
continue

# 海なら埋め立て、つながるかどうか確認する。
field[fy][fx] = 'o'
if land_connectedp(field):
print('YES')
return
field[fy][fx] = 'x'

# 条件に合う埋立地が見つからなければ、NO
print('NO')

main()
Share

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です