CR.BFS1 for Python

main.py

from collections import deque


# The start cell in (0, 0) should be 1 for funniness:
m = [[0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 1, 0],
     [0, 0, 1, 0, 0, 0],
     [0, 0, 0, 0, 0, 1],
     [0, 0, 0, 0, 1, 0],
     [1, 0, 1, 0, 0, 0],
     [1, 0, 0, 0, 0, 1],
     [0, 0, 0, 0, 1, 0],
     [1, 0, 1, 0, 0, 0]]

visited = []
queue = []

parent = {}
num = 0


def generate_neighbours(maze, cell):

    def _is_valid(maze, x, y):
        maze_width = len(maze[0])
        maze_height = len(maze)

        return 0 <= x < maze_width and 0 <= y < maze_height

    x, y = cell

    for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        next_x = x + dx
        next_y = y + dy

        if _is_valid(maze, next_x, next_y):
            yield next_x, next_y


def coderodde_bfs(maze, source):

    def _traceback_path(tail, parents):
        path = []
        current = tail

        while current:
            path.append(current)
            current = parents[current]

        path.reverse()
        return path

    def _is_goal_state(maze, current):
        x = current[0]
        y = current[1]

        return maze[y][x] == 1

    queue = deque([source])
    parents = {source: None}

    while queue:
        current = queue.popleft()

        if _is_goal_state(maze, current):
            return _traceback_path(current, parents)

        for neighbour in generate_neighbours(maze, current):
            if neighbour not in parents:
                parents[neighbour] = current
                queue.append(neighbour)

    return None

def breadth_first(maze, x, y):
    queue.append((x, y))
    visited.append((x, y))

    while queue:
        pos = queue[0]
        x = pos[0]
        y = pos[1]

        # remove from queue
        queue.remove(pos)

        # find neighbor
        for dir_x, dir_y in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            newx = x + dir_x
            newy = y + dir_y

            neighbor = (newx, newy)

            # add to queue
            if len(maze[0]) > newx >= 0 and len(maze) > newy >= 0 and neighbor not in visited and neighbor not in queue:
                if m[newy][newx] == 1:
                    parent[neighbor] = pos
                    return neighbor

                queue.append(neighbor)
                visited.append(neighbor)
                parent[neighbor] = pos


closest = breadth_first(m, 0, 0)

path = [closest]


def search(traceback):
    while traceback != (0, 0):
        for key, value in parent.items():
            if traceback == key:
                path.append(value)
                traceback = value

    return path


def solved(maze, input_path):
    for pos in input_path[1:-1]:
        maze[pos[1]][pos[0]] = '+'

    return maze

print(coderodde_bfs(m, (0, 0)))