AtCoder Grand Contest 033 A – Darker and Darker をPython3で解く

Share

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

出典:
AtCoder Grand Contest 033 A – Darker and Darker

毎回全てを探索するのではなく、その時々で必要な部分だけを探索していく、という問題。

# AtCoder Grand Contest 033 A - Darker and Darker
# https://atcoder.jp/contests/agc033/tasks/agc033_a
# グリッド キュー BFS

# 毎回グリッドを全て探索していては、間に合わない。
# ところで、毎回の操作で黒マスが少しずつ増えていくわけだが、
# その操作で黒マスになるのは、前回の操作で黒マスになった
# 地点の隣だけである。

# つまり、毎回全マスを探索するのではなく、前回黒マスになった
# 隣のマスだけを探索すればいい。これは一種のBFSとなる。
# 均すと、全てのマスは一回ずつ探索されることになるので
# O(HW) となる。

from collections import deque
def main():
H, W = map(int, input().split())
field = [[c for c in input()] for _ in range(H)]

moves = ((-1, 0), (1, 0), (0, -1), (0, 1))

# 黒マスに変わった手数を保存しておく配列。
# まだ白マスなら -1。
done = [[-1] * W for _ in range(H)]

# 初回のキューの作成
queue = deque()
for y in range(H):
for x in range(W):
if field[y][x] == '#':
queue.append((x, y))
done[y][x] = 0

result = 0

# 探索開始
while queue:
x, y = queue.pop()
for dx, dy in moves:
tx, ty = x + dx, y + dy

# 黒マスの隣がまだ白なら、黒マスに変えてキューの左に追加。
if 0 <= tx < W and 0 <= ty < H and done[ty][tx] == -1:
done[ty][tx] = done[y][x] + 1
queue.appendleft((tx, ty))
if result < done[ty][tx]:
result = done[ty][tx]

print(result)

main()

以下ちょっとだけ解き方を変えたオマケ。

# deque を使用せず、次回探索用のリストを作成し、
# 切り替えていく方式でも解ける。ついでに番兵法も用いてみた。
def main():
H, W = map(int, input().split())

# 番兵を置いておく。
# pythonは list[-1] で最後尾になるので、
# 置くのは一つだけでいい。
field = [[c for c in input()] + ['#'] for _ in range(H)]
field.append(['#'] * (W+1))

moves = ((-1, 0), (1, 0), (0, -1), (0, 1))

# 初回のキューの作成
queue = []
for y in range(H):
for x in range(W):
if field[y][x] == '#':
queue.append((x, y))

result = 0

# ここから探索。
while True:
new_queue = []
for x, y in queue:
for dx, dy in moves:
tx, ty = x + dx, y + dy
if field[ty][tx] == '.':
field[ty][tx] = '#'
new_queue.append((tx, ty))

# キューの更新。
queue = new_queue

if len(queue) > 0:
result += 1
else:
break

print(result)

main()

Share

コメントを残す

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