Hi everyone,
I am trying to solve the problem BITMAP: http://www.spoj.com/problems/BITMAP/ using python. However I keep getting a TLE on submission of my code. I am at a loss regarding how to speed it up any further. I would be very grateful for any hints about how to optimize the code to get that coveted AC! I am relatively new to python and SPOJ so any other constructive suggestions regarding the code are welcome as well.
Thank you
The Code:
pos_X = [0,1,0,-1]
pos_Y = [-1,0,1,0]
def is_valid(i,j,k,r,c):
if i+pos_X[k] < 0 or i+pos_X[k] > r-1:
return False
if j+pos_Y[k] < 0 or j+pos_Y[k] > c-1:
return False
else:
return True
def calc(item,r,c):
i,j=item[0],item[1]
append_queue=[]
for k in xrange(0,4):
if is_valid(i,j,k,r,c):
if dp[i+pos_X[k]][j+pos_Y[k]] > 1+ dp[i][j]:
dp[i+pos_X[k]][j+pos_Y[k]] = 1+ dp[i][j]
append_queue.append([i+pos_X[k],j+pos_Y[k]])
return append_queue
for k in xrange(0,int(raw_input())):
M_N=map(int,raw_input().split())
M=M_N[0]
N=M_N[1]
array=[]
dp=[]
dist_queue=[]
for i in xrange(0,M):
line = map(int,list(raw_input()))
dp_array=[]
for j in xrange(0,N):
if line[j]==1:
dist_queue.append([i,j])
dp_array.append(0)
else:
dp_array.append(float('inf'))
array.append(line)
dp.append(dp_array)
while len(dist_queue)>0:
append_queue = calc(dist_queue.pop(0),M,N)
dist_queue=dist_queue+append_queue
for i in xrange(0,M):
for j in xrange(0,N):
print dp[i][j],
print ''
raw_input()
