import random, sys, os sys.setrecursionlimit(100000) n,m = 21,21 pos = 0,0 dest = (11,9) tempmaze,maze,besttempmaze = [] , [] , [] lastpos = None 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]=2 def 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 nb def 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(): r="" for row in tempmaze: for block in row: if str(block[0])=="1": r+="#" elif str(block[0])=="2": r+="F" else: r+="." r+="\n" return r[:-1] 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=bob def 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= (1,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): pass def 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 home def clearseen(): global tempmaze for a in tempmaze: for b in a: a[1]=0 def 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 retl stack = [] def dfs(): def findpath(): global pos global dest global stack # This eats O(intersections) stack val = valid(neighbours0(pos[0],pos[1])) try: if val.count(stack[-1]): val.remove(stack[-1]) except IndexError: # Should possibly only happen on the first entry pass if val: stack.extend(pos) for path in val: search(path) pos = path if (pos == dest): return True elif findpath(): return True else: findpath() pos = stack.pop() return False findpath() def search(gotoa): global pos if gotoa[1]==pos[1]: #left or right if gotoa[1]