This page looks best with JavaScript enabled

AGC 033 A-Darker and Darker (失敗

 ·   ·  ☕ 1 min read  ·  ✍️ reud · 👀... views

解けなかったので、復習していきたいです。

けんちょんさんの記事が非常にわかりやすいのでこちらを見てから

ここはPythonの実装と個人的なメモみたいな感じで書き残していきたいと思います。

解けて無いです。

これがTLE解 

setが遅いかな もう何もわからないよ・・・(完)

def dig(tag,end):
    h=tag[0]
    w=tag[1]
    delta=[(1,0),(-1,0),(0,1),(0,-1)]
    next=set()
    for d in delta:
        if not h+d[0]<0 and not h+d[0]>=H and not w+d[1]<0 and not w+d[1]>=W and tag not in end:
            next.add((h+d[0],w+d[1]))
    return next

H, W = map(int, input().split())
black_mass=set()

for h in range(H):
    line=input()
    for w in range(W):
        if line[w] == '#':
            black_mass.add((h,w))

count=-1
end=set()
targets=black_mass
next_que=set()
while True:
    count+=1
    next_que=set()
    for tag in targets:
        next_que= next_que | dig(tag,end)
        end.add(tag)
    # print('next que',next_que)
    # print('end:',end)
    targets=next_que
    if len(end) == H*W:
        print(count)
        exit(0)
Share on

reud
WRITTEN BY
reud
Stundent