Something

# I hereby acknowledge that the work handed in is my own original work. If I
# have quoted from any other source this information has been correctly
# referenced. If I was in any doubt as to what constituted plagiarism I have
# read the university policy on plagiarism in the "statute and policies" at
# www.uct.ac.za.
# 
# Name: Ben Steenhuisen
# Assignment: AI Client
# Date: 29/April/2007

# Ai Client..
# Insert plag stuff here..

import random
import sys

n,m = 21,21
pos = 0,0
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 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():
	pass

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:
		if tempmaze[((e[0]+pos[0])/2)][((e[1]+pos[1])/2)][0]==0:
			retl.append((e[0],e[1]))
	return retl
	

def dfs():
	stack = []
	tree = []  
	global pos
	dest = (2,2) 
	stack.append(valid(neighbours0(pos[0],pos[1])))
	search(stack.pop(0))
	while stack and ((dest[0],dest[1])!=(pos[0],pos[1])):
		cur =stack.pop(0)
		if tempmaze[pos[0]][pos[1]][1]==0:
			stack.append(neighbours0(pos[0],pos[1]))
			search(cur)
			
def search(gotoa):
	global pos
	if gotoa[0]==pos[0]:
		#left or right
		if gotoa[1]>pos[1]:
			print "E"
		else:
			print "W"
	else:
		if gotoa[0]>pos[0]:
			print "S"
		else:
			print "N"
		
		  #up or down

tempmazegen(21,21)
print printer0()
clearseen()
dfs()