Breadth First Search in python

bfs.py

#!/usr/bin/python

# Head ends here
from collections import deque
class Node:
    def __init__(self, point,parent=None):
        self.point = point
        self.parent = parent

explored = []
def nextMove( x, y, pacman_x, pacman_y, food_x, food_y, grid):
    node = bfs(Node((pacman_x,pacman_y)),(food_x,food_y),(x,y),grid)
    if node != None:
        print len(explored)
        print '\n'.join([str(i[0]) + " " + str(i[1]) for i in explored])
        path = []
        while node != None:
            path.append(node.point)
            node = node.parent
        path.reverse()
        print len(path) - 1
        print '\n'.join([str(i[0]) + " " + str(i[1]) for i in path])
    return

def children(point,size,grid):
    x,y = point
    size_x, size_y = size
    children = [(x-1, y),(x,y - 1),(x,y + 1),(x+1,y)]
    return [child for child in children if grid[child[0]][child[1]] != '%']
            
def bfs(node,goal,size,grid):
    queue = deque()
    queue.append(node)
    explored.append(node.point)
    while queue:
        t = queue.popleft()
        if t.point not in explored:
            explored.append(t.point)
        if t.point == goal:
            return t
        for child in children(t.point,size,grid):
            if child not in explored:
                u = Node(child,t)
                queue.append(u)
    return None
# Tail starts here

pacman_x, pacman_y = [ int(i) for i in raw_input().strip().split() ]
food_x, food_y = [ int(i) for i in raw_input().strip().split() ]
x,y = [ int(i) for i in raw_input().strip().split() ]

grid = []
for i in xrange(0, x):
    grid.append(raw_input().strip())

nextMove(x, y, pacman_x, pacman_y, food_x, food_y, grid)