class matrix(object):
	def  __init__(self,w,h,fill=None):
		self.mx = {}
		self.w,self.h = w-1,h-1
		for x in range(w):
			for y in range(h):
				self.mx[(x,y)] = fill
	
	def all(self):
		return self.mx.keys()
	
	def at(self,x,y=None,fill=None):
		if y == None:
			(x,y) = x
		if (x,y) in self.mx:
			if fill:
				self.mx[(x,y)] = fill
			return self.mx[(x,y)]
		return None

	def neighbor(self,x,y=None):
		if y == None:	(x,y) = x
		left,right,up,down = None,None,None,None
		if x>0:		left = (x-1,y)
		if y>0:		up = (x,y-1)
		if x<self.w:	right = (x+1,y)
		if y<self.h:	down = (x,y+1)
		return [up,down,left,right]
	
	def four_corner(self,x,y=None):
		if y == None :	(x,y) = x
		ul,ur,dl,dr = None,None,None,None
		if x>0 and y>0:			ul = (x-1,y-1)
		if x>0 and y<self.h:		dl = (x-1,y+1)
		if x<self.w and y>0:		ur = (x+1,y-1)
		if x<self.w and y<self.h:	dr = (x+1,y+1)
		return [ul,ur,dl,dr]
	
	def around(self,x,y=None):
		if y == None:	(x,y) = x
		return self.neighbor(x,y) + self.four_corner(x,y)

	def node(self,src,dest,p_coord,p_cost,cost=None):
		if cost:
			c = cost(self.at(src[0],src[1]))
		else:
			c = 1
		if c:
			h = abs(src[0]-dest[0]) + abs(src[1]-dest[1])
			g = p_cost + c
			f = g + h
			return (f,g,h,p_coord)
		return None
	
	def findpath(self,src,dest,cost=None):
		node = self.node(src,dest,src,0,cost)
		if not node:
			return None
		opened = {src:node}
		closed = {}
		best = src
		while best != dest:
			if len(opened) == 0:
				return None
			for index in opened:
				if best in opened:
					if opened[index][0] < opened[best][0]:
						best = index
				else:
					best = index
			closed[best] = opened.pop(best)
			for neighbor in self.neighbor(best):
				if neighbor:
					node = self.node(neighbor,dest,best,closed[best][1],cost)
					if node:
						if neighbor in closed:
							if closed[neighbor][1] > node[1]:
								closed.pop(neighbor)
								closed[neighbor] = node
						elif neighbor in opened:
							if opened[neighbor][1] > node[1]:
								opened.pop(neighbor)
								opened[neighbor] = node
						else:
							opened[neighbor] = node
		#return closed
		final = []
		current = dest
		while current != src:
			final.append(current)
			current = closed[current][3]
		final.append(src)
		return final

if __name__ == "__main__":
	m = matrix(13,13)
	for x in range(0,13):
		m.at(x,0,True)
		m.at(x,12,True)
		m.at(12,x,True)
		m.at(0,x,True)
	maze = [(2,1),(2,2),(2,3),(2,4),(2,5),\
		(1,7),(2,7),(3,7),(4,7),(4,6),(4,5),(4,4),(4,3),(4,2),\
		(1,9),(2,9),(3,9),(4,9),(5,9),(6,9),(6,8),(6,7),(6,6),(6,5),\
		(11,10)
	]
	
	for i in maze:
		m.at(i[0],i[1],True)
	
	def obstacle(nud):
		if nud == True:
			return None
		return 2
	
	p = m.findpath((1,1),(11,11),obstacle)
	
	if not p:
		print "failed"
	else:
		for y in range(m.h):
			t = ""
			for x in range(m.w):
				if (x,y) == (1,1):
					t=t+"[s]"
				elif (x,y)==(11,11):
					t=t+"[g]"
				elif (x,y) in p:
					t = t + "[.]"
				elif m.at(x,y):
					t = t + "[#]"
				else:
					t = t + "[ ]"
			print t