import random, sys, os

# XXX: DEBUG
from time import sleep

sys.setrecursionlimit(100000)

n,m = 21,21
pos = (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]=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 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 res


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():
    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))
    res.append("Dest: %s Pos: %s" % (str(dest), str(pos)))
    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=bob

def opening0():
    possible = [e for e in xrange(1,n) if (e%2==1) and not tempmaze[1][e][0]]
    tempmaze[0][possible[0]][0]=0
    global dest
    dest = (possible[0], 1)


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:
            b[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

def 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 res

stack = []
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.2)
        #os.system('clear')

        if pos == dest:
            print printer0()
            print "FINISHED!"
            return True
        if val:
            for path in val:
                stack.append(pos)
                #search(path)
                pos = path
                if findpath():
                    return True
                pos = stack.pop()
                # XXX: DEBUG
                #print printer0()
                #sleep(0.2)

        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 down



tempmazegen(21,21)
opening0()

#print printer0()
#print repr(tempmaze)
clearseen()
os.system('clear')
dfs()