python - SPOJビットマップ（BFS）

Question

私はPythonを使用してspojの問題を解決しようとしています。私のアルゴリズムはO（n ^ 2）のみである必要がありますが、それでもTLEが返されます...
私のメソッドは単なるマルチソースBFSです。

1. すべての1の位置を見つける
2. 各「1」でBFSを実行し、最短距離を「ans」という名前の2Dリストに格納します
3. ansを印刷する

問題のリンク：http ：//www.spoj.pl/problems/BITMAP/

if __name__ == '__main__':
    n = int(input())    #reading number of test cases
    for k in range(n): 
        (row, col) = input().split()    #row and col
        row = int(row)
        col = int(col)
        #store the bitmap
        bitmap = []
        for i in range(row):
            line = input()
            bitmap.append(line)
        ans = [[False for i in range(col)] for j in range(row)]     #init a 2d array to store answer
        front = []
        num_element = row*col
        processed = 0
        for i in range(row):
            for j in range(col):
                if(bitmap[i][j] == '1'):
                    ans[i][j] = 0
                    front.append((i,j))
                    processed = processed +1
        while processed < num_element:
            new_list = []
            for node in front:
                i = node[0]
                j = node[1]
                new_distance = ans[i][j] + 1
                if(i> 0 and ans[i-1][j] is False):
                    ans[i-1][j] =new_distance                    
                    new_list.append((i-1,j))
                    processed = processed +1
                if(i< row -1 and ans[i+1][j] is False):
                    ans[i+1][j] =new_distance
                    new_list.append((i+1,j))
                    processed = processed +1
                if(j > 0 and ans[i][j-1] is False):
                    ans[i][j-1] =new_distance
                    new_list.append((i,j-1))
                    processed = processed +1
                if(j < col -1 and ans[i][j+1] is False):
                    ans[i][j+1] =new_distance
                    new_list.append((i,j+1))
                    processed = processed +1
            front = new_list
        #print the answer
        for line in ans:
            s = map(str, line)
            print(" ".join(s))
        input()

Answer 1

マンハッタン距離を使用して距離変換を計算する必要があります。この記事は、ユークリッド距離の線形（O（rows * cols））アルゴリズムのスケッチを表しています（ただし、マンハッタンのものも言及されています）。

Answer 2

ありがとうございました。私はついに同じアルゴリズムをC++で実装し、受け入れました！問題が必要なようです2D配列はPythonには適していません。