dfs.py

#!/usr/bin/python

#class Node:
#    def __init__(self,point,parent=None):
#        self.point = point
#        self.parent = parent
        
# Head ends here
explored = []
def nextMove( x, y, pacman_x, pacman_y, food_x, food_y, grid):
    path = []
    if dfs((pacman_x,pacman_y),(food_x,food_y),(x,y),grid,path):
        print len(explored)
        print '\n'.join([str(i[0]) + " " + str(i[1]) for i in explored])
        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 child[0] >= 0 and child[1] >= 0 and child[0] < size_x and child[1] < size_y and grid[child[0]][child[1]] != '%']
            
def dfs(node,goal,size,grid,result):
    if node in result:
        return False
    if node not in explored:
        explored.append(node)
    result.append(node)
    if node == goal:
        return True
    for child in reversed(children(node,size,grid)):
        if dfs(child,goal,size,grid,result):
            return True
    result.pop()
    return False
# 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)