AtCoder Grand Contest 033 A - Darker and Darker のPython3での計算量について

Question

以下のようなコードを書きました。計算量がO(N)になっていると考えていて、PyPyなら十分通ると考えているのですが、ほとんどの結果がTLEになってしまいます。　計算時間を短縮し、ACする方法はあるのでしょうか。

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)

Answer 1

PHPで通したコードに発想が似ているので、Python3で組み直してみたんですけど、TLEになりますね。
（Pythonは初心者です）

# coding: utf-8
 
import copy
 
H, W = map(int, input().split())
rest = H * W
lst = [[0 for i in range(W)] for j in range(H)]
answer = 0
 
black_mass = set()
new_black_mass = set()
 
for h in range(H):
    line=input()
    for w in range(W):
        if line[w] == '#':
            rest -= 1
            lst[h][w] = 1
            black_mass.add((h,w))
 
while(rest > 0):
    for xy in black_mass:
        if xy[0] > 0:
            if lst[xy[0]-1][xy[1]] == 0:
                lst[xy[0]-1][xy[1]] = 1
                new_black_mass.add((xy[0]-1, xy[1]))
                rest -= 1
        if xy[0] < H - 1:
            if lst[xy[0]+1][xy[1]] == 0:
                lst[xy[0]+1][xy[1]] = 1
                new_black_mass.add((xy[0]+1, xy[1]))
                rest -= 1
        if xy[1] > 0:
            if lst[xy[0]][xy[1]-1] == 0:
                lst[xy[0]][xy[1]-1] = 1
                new_black_mass.add((xy[0], xy[1]-1))
                rest -= 1
        if xy[1] < W - 1:
            if lst[xy[0]][xy[1]+1] == 0:
                lst[xy[0]][xy[1]+1] = 1
                new_black_mass.add((xy[0], xy[1]+1))
                rest -= 1
    black_mass.clear()
    black_mass = copy.copy(new_black_mass)
    answer += 1
 
print(answer)

手元で実行したところ、in01.txtで40秒近くかかってました。
計算量自体はPHPのときと同じのはずなので、Pythonの処理系の中で遅いデータ処理の仕方になっているんじゃないかなー、と思います。

ACした人のPythonコードを見てみたんですが、NumPyとかSciPy使ってる人が多いですね。
それ以外の人のコードを、もう少し探してみたいと思います。

Answer 2

Atcoderでは、「詳細」から他の回答者の回答(コード)を見ることができます。

以下のリンクにACの回答者リストがあるので、その中から何人かの回答を見てみてはどうでしょうか。「詳細」は回答者リストの右側に載っています。

https://atcoder.jp/contests/agc033/submissions?f.Task=agc033_a&f.Language=3510&f.Status=AC&f.User=

ご参考になれば幸いです。