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()







