import collections
wall,clear,goal = 0, 1, 9
grid1 = ['100',
        '100',
        '119']
width, hight = 3, 3


def bfs(grid, start):
        queue = collections.deque([[start]])
        seen = set([start])
        while queue:
                path = queue.popleft()
                x,y = path[-1]
                if grid[y][x] == goal:
                        return path
                for x2, y2 in ((x+1, y), (x-1, y), (x, y+1), (x, y-1)):
                        if 0 <= x2 < width and 0 <= y2 < hight and grid[y2][x2] != wall and (x2, y2) not in seen:
                                queue.append(path + [(x2, y2)])
                                seen.add((x2, y2))
                                print("in 2nd loop", path)


path = bfs(grid1, (0, 0))