import random, sys, os# XXX: DEBUGfrom time import sleepsys.setrecursionlimit(100000)n,m = 21,21pos = (0,0)dest = (11,9)tempmaze,maze,besttempmaze = [] , [] , []def doer0(): global tempmaze init0() gen_tempmaze0((((n-1)/4*2)-1,((n-1)/4*2)-1)) for x in xrange(2): reshuffle0() #just to make it extra-shuffled :-) #reshuffle0() opening0() tempmaze[(n-3)/2][(m-3)/2][0]=2def init0(): for i in xrange(n): row = [] for j in xrange(m): row.append([1, 0]) tempmaze.append(row)def gen_tempmaze0(pos): global tempmaze,m,n tempmaze[pos[0]][pos[1]][1] = 1 nb = neighbours0(pos[0], pos[1]) unvisited = [a for a in nb if not tempmaze[a[0]][a[1]][1]] if unvisited: p = unvisited[random.randint(0, len(unvisited) - 1)] tempmaze[p[0]][p[1]][0] = 0 tempmaze[(p[0]+pos[0])/2][(p[1]+pos[1])/2][0]=0 gen_tempmaze0(p)def neighbours0(x, y): nb = [] for i in [-2, 0, 2]: for j in [-2, 0, 2]: if (i == 0 or j == 0) and not (i == 0 and j == 0) and 0 <= x + i < n and 0 <= y + j < m: nb.append((x + i, y + j)) return nbdef neighbours1(x, y): res = [] checklist=((x-1, y), (x, y+1), (x+1, y), (x, y-1)) for pt in checklist: if 0 <= pt[0] < n and 0 <= pt[1] < m: res.append(pt) return resdef reshuffle0(): NewList=[] for e in xrange(n): for f in xrange(m): if (e % 2==1 and f%2 ==1): NewList.append((e,f)) random.shuffle(NewList) for e in NewList: if tempmaze[e[0]][e[1]][0]==0: gen_tempmaze0((e[0],e[1]))def printer0(): res = [] for x in xrange(0, n): row = [] for y in xrange(0, m): if (x, y) == pos: row.append('F') elif tempmaze[x][y][0] == 1: row.append('#') else: row.append('.') res.append("".join(row)) return "\n".join(res)def flip(): global tempmaze #sssssssssssigh.. this is not kewl.. bob=[] for row in tempmaze: bob.append(row) bob.reverse() ##if only we remembered this for standard bank it challenge we could have won :( tempmaze=bobdef opening0(): possible = [e for e in xrange(1,n) if ((e%2==1) and (tempmaze[1][e]))] tempmaze[0][possible[0]][0]=0 global des dest= (0, possible[0])def tempmazegen(an,am): global n,m,pos n,m=an,am pos=(((n-3)/2) , ((m-3)/2)) doer0()def navi(b,start,finish): passdef play(): pass ## get player number ## generate lots of mazes ## choose best one ## flip if player 1, not 0 ## dfs to no-mans land ## dfs to enemy flag ## dfs homedef clearseen(): global tempmaze for a in tempmaze: for b in a: b[1]=0def valid(lis): retl=[] global pos,tempmaze for e in lis: #print e if tempmaze[((e[0]+pos[0])/2)][((e[1]+pos[1])/2)][0]==0: retl.append((e[0],e[1])) #print retl return retldef get_outs(where): res = [] ns = neighbours1(where[0], where[1]) for neigh in ns: #print "Maze:", tempmaze[neigh[0]][neigh[1]] if tempmaze[neigh[0]][neigh[1]][0]!=1: res.append(neigh) return resstack = []def dfs(): def findpath(): global pos global dest global stack # This eats O(intersections) stack val = get_outs(pos) try: val.remove(stack[-1]) except IndexError: pass #print "Stack:", stack # XXX: DEBUG print printer0() sleep(0.6) #os.system('clear') if val: for path in val: stack.append(pos) #search(path) pos = path if (pos == dest): return True if findpath(): return True pos = stack.pop() return False findpath()def search(gotoa): global pos if gotoa[1]==pos[1]: #left or right if gotoa[1]<pos[1]: print "S"*2 else: print "N"*2 else: if gotoa[0]<pos[0]: print "W"*2 else: print "E"*2 #up or downtempmazegen(21,21)opening0()#print printer0()#print repr(tempmaze)clearseen()os.system('clear')dfs()