Here is my code in python and I get TLE
What I do is simply run BFS in each cell
I try to write some comment to explain my code. Thank YOu
http://www.spoj.pl/problems/BITMAP/
if __name__ == '__main__':
n = int(input()) #reading number of test cases
for k in range(n):
if k > 0:
input() #read the empty line after one test case
(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)
max_round = row + col #max step to find a '1'
ans = [[0 for i in range(col)] for j in range(row)] #init a 2d array to store answer
front = [] #A list that storing the target cell in each round
for i in range(row):
for j in range(col):
if bitmap[i][j] == '1': #current cell is 1, simply set 0 for answer
ans[i][j]= 0
else:
current_step = 0
found = False
front.append((i, j))
max_step = max_round
#As the top-left cell have calculated already, distance = ans of that cell + 1
if(i >0 ):
max_step = min(max_round,ans[i-1][j]+1)
if(j > 0):
max_step = min(max_step,ans[i][j-1]+1)
#Test for every possible distance(BFS)
for current_round in range(max_step):
for pair in front:
#test right cell
if(pair[0] < row - 1 and bitmap[pair[0] + 1][ pair[1]] == '1'):
ans[i][j]=current_round + 1
found = True
break
#test cell below
if(pair[1] < col - 1 and bitmap[pair[0]][pair[1] +1] == '1'):
ans[i][j]=current_round + 1
found = True
break
#reset the target list
front = []
if found == True:
break
#put the next targets
if(pair[0]+1 < row):
front.append((pair[0]+1,pair[1]))
if(pair[1]+1 < col):
front.append((pair[0],pair[1]+1))
if(found == False):
ans[i][j]= int(max_step)
#print the answer
for line in ans:
s = map(str, line)
print(" ".join(s))
