http://codeforces.me/contest/515/problem/D http://codeforces.me/contest/515/submission/21582967 Im getting a tle on test 18. Is there anything I can do to improve this vs rewriting in c++? I added the ct/z flags to make sure I save 1 extra loop in the case that I filled all tiles or produced no degree 1 edges. I implemented the same strategy as in their editorial but somehow it is too slow. (http://codeforces.me/blog/entry/16468) ideas? ~~~~~ from Queue import Queue
def main(): q = Queue() n, m = map(int,raw_input().split()) grid = [list(raw_input()) for x in xrange(n)] z = True while z: ct=0 z = False for r in xrange(n): for c in xrange(m): if grid[r][c] == '*': ct+=1 if grid[r][c] == '.': deg = 0 up = left = right = down = False if c+1<m and grid[r][c+1] == '.': deg +=1 right = True if r+1<n and grid[r+1][c] == '.': deg +=1 down = True if r-1>=0 and grid[r-1][c] == '.': deg +=1 up = True if c-1>=0 and grid[r][c-1] == '.': deg +=1 left = True if deg == 1: z = True #if we hit a degree 1 we may have created another if left: q.put((r,c-1,'<')) q.put((r,c,'>')) grid[r][c-1] = '@' #mark this so we dont overwrite it #with another configuration and skip it in the main loop if up: q.put((r-1,c,'^')) q.put((r,c,'v')) grid[r-1][c] = '@' if down: q.put((r,c,'^')) q.put((r+1,c,'v')) grid[r+1][c] = '@' if right: q.put((r,c,'<')) q.put((r,c+1,'>')) grid[r][c+1] = '@'
if(q.qsize()+ct) >= n*m:
z = True
break
if z == False:
print "Not unique"
return
while q.empty() == False:
x,y,s = q.get()
if grid[x][y] == '.' or grid[x][y] == '@':
grid[x][y] = s
else:
continue
for i in grid:
print ''.join(i)if name == '__main__': main()
~~~~~




