Python Code

class Node :
def __init__(self, name) :
self.name = name
self.up = None
self.down = None
self.left = None
self.right = None
self.up_weight = None
self.down_weight = None
self.left_weight = None
self.right_weight = None
def view(self, node) :
ret = {'Current' : node.name}
if node.up :
ret['up'] = node.up.name
ret['up_weight'] = node.up_weight
if node.down :
ret['down'] = node.down.name
ret['down_weight'] = node.down_weight
if node.left :
ret['left'] = node.left.name
ret['left_weight'] = node.left_weight
if node.right :
ret['right'] = node.right.name
ret['right_weight'] = node.right_weight
return ret
class Graph :
def __init__(self) :
self.start = None
self.end = None
def markstart(self, n) :
nd = Node(n)
self.start = nd
return nd
def markend(self, n) :
nd = Node(n)
self.end = nd
return nd
def insert(self, new, weight=1) :
n = Node(new)
return n
def oldinsert(self, oldnode, direction, new, weight) :
n = Node(new)
if direction == 'U' :
oldnode.up = n
n.down = oldnode
oldnode.up_weight = n.down_weight = weight
return n
if direction == 'D' :
oldnode.down = n
n.up = oldnode
oldnode.down_weight = n.up_weight = weight
return n
if direction == 'L' :
oldnode.left = n
n.right = oldnode
oldnode.left_weight = n.right_weight = weight
return n
if direction == 'R' :
oldnode.right = n
n.left = oldnode
oldnode.right_weight = n.left_weight = weight
return n
def reached(self, n) :
if self.end == n :
return True
return False
class Queue :
def __init__(self) :
self.queue = list()
def insert(self, value) :
self.queue.append(value)
def pop(self) :
if self.queue :
return self.queue.pop(0)
return
def isEmpty(self) :
if self.queue :
return False
return True
def createnodes(matrix, n) :
print("Cresting Maze, Please Wait.", end = '\r')
dicta = dict()
graph = Graph()
for i in range(1, (n*n)+1) :
if i == 1 :
dicta[i] = graph.markstart(i)
elif i == n*n :
dicta[i] = graph.markend(i)
elif matrix[xycord(i, n)[0]][xycord(i, n)[1]] == 1 :
dicta[i] = graph.insert(i)
directions = 'UDRL'
for x in directions :
temp = enumerators(i, x, n)
if temp :
if dicta.get(temp) :
relate(x, dicta[i], dicta[temp])
return dicta, graph
def enumerators(curr, dirt, n) :
if dirt == 'U' :
if curr-n >= 1:
return curr-n
else:
return
if dirt == 'D' :
if curr+n <= n*n:
return curr+n
else:
return
if dirt == 'R' :
if (curr)%n != 0 :
return curr+1
else:
return
if dirt == 'L' :
if curr%n != 1:
return curr-1
else:
return
def relate(x, n, dicta, weight = 1) :
if x == 'U' :
n.up = dicta
dicta.down = n
n.up_weight = weight
dicta.down_weight = weight
elif x == 'L' :
n.left = dicta
dicta.right = n
n.left_weight = weight
dicta.right_weight = weight
elif x == 'R' :
n.right = dicta
dicta.left = n
n.right_weight = weight
dicta.left_weight = weight
elif x == 'D' :
n.down = dicta
dicta.up = n
n.down_weight = weight
dicta.up_weight = weight
def xycord(i, n) :
i = i-1
x = i//n
y = i%n
return x, y
def BFS(graph, visitdict, dicta, n) :
queue = Queue()
queue.insert(graph.start)
directions = 'LDRU'
poped = graph.start
while not queue.isEmpty() and not graph.reached(poped):
poped = queue.pop()
if visitdict[poped.name] == False :
visitdict[poped.name] = True
print(poped.name)
for i in directions :
temp = enumerators(poped.name, i, n)
if visitdict.get(temp) != None visitdict[temp] == False :
queue.insert(dicta[temp])
import time
infinity = 2**32
if __name__ == "__main__" :
matrix, n = [[1,1,1,1,1], [1,1,1,1,1], [1,1,1,1,1], [1,1,1,1,1], [1,1,1,1,1]], 5
dictofnodes, graph = createnodes(matrix, n)
visitdict = dict()
costdict = dict()
for i in dictofnodes.keys() :
visitdict.setdefault(i, False)
costdict.setdefault(i, infinity)
print(dictofnodes.keys())
t = time.perf_counter()
BFS(graph, visitdict,dictofnodes, n)