vipul_sarin1
Jul '15

Hi everyone,

I am trying to solve the problem BITMAP: http://www.spoj.com/problems/BITMAP/1 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()