我尝试使用python解决 spoj 问题。我的算法应该只有O(n^2)，但仍然返回TLE ......
我的方法只是一个多源 BFS。
- 找出所有1的位置
- 在每个“1”上运行 BFS，将最短距离存储到名为“ans”的 2D 列表中
- 打印答案
问题链接：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()