class DFS():
    ''' start the search '''
    def search(self, start, end, graph):
        self._fringe = [(start, [])]
        self._visited = []
        while len(self._fringe) > 0:
            node = self._getNext()
            if node is None:
                break
            elif node[0] is not end:
                for neighbour in graph[node[0]]:
                    self._fringe.append((neighbour, node[1]+[node[0]]))
            else:
                return node[1] + [node[0]]
        return None

    ''' Returns the next node from fringe '''
    def _getNext(self):
        while len(self._fringe) > 0:
            node = self._fringe.pop()
            if node[0] not in self._visited:
                self._visited.append(node[0])
                return node
        return None

class BFS(DFS):
    def _getNext(self):
        while len(self._fringe) > 0:
            node = self._fringe.pop(0)
            if node[0] not in self._visited:
                self._visited.append(node[0])
                return node
        return None

maze = [
 [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
 [1,1,1,1,0,1,1,1,1,0,1,1,1,1,0],
 [0,0,0,1,0,1,0,0,0,0,1,0,0,0,0],
 [0,1,0,0,0,0,0,1,1,0,1,0,1,1,1],
 [0,1,0,1,1,1,0,0,1,0,1,0,0,0,0],
 [0,1,0,0,0,1,1,1,1,0,1,1,1,1,0],
 [0,1,1,1,0,0,0,0,0,0,0,1,0,0,0],
 [0,1,0,1,1,1,1,1,1,0,1,0,0,1,1],
 [0,1,0,1,1,0,1,0,1,0,1,0,1,1,1],
 [0,1,0,0,0,0,0,0,1,0,1,0,0,0,0],
 [0,1,0,1,1,1,1,0,1,0,1,1,1,1,0],
 [0,1,0,1,0,0,1,0,1,0,1,0,0,0,0],
 [0,1,0,1,0,1,1,0,1,0,1,1,1,1,1],
 [0,1,0,1,0,1,1,0,1,0,0,0,0,0,0],
 [0,0,0,1,0,0,0,0,0,0,1,1,1,1,0]]

graph = [[] for x in range(pow(15,2))]
for node in range(len(graph)):
    x = node % 15
    y = node / 15
    if maze[x][y] is 0:
        if x > 0:
            if maze[x-1][y] == 0:
                graph[node].append(node-1)
        if x < 14:
            if maze[x+1][y] == 0:
                graph[node].append(node+1)
        if y > 0:
            if maze[x][y-1] == 0:
                graph[node].append(node-15)
        if y < 14:
            if maze[x][y+1] == 0:
                graph[node].append(node+15)


bfs = BFS()
dfs = DFS()

bfsPath = bfs.search(0,224,graph)

dfsPath = dfs.search(0,224,graph)