title: Find the path for Pacman from expanded/explored nodes
body: <p>I implemented a BFS for Pacman. I am getting correct list for nodes expanded. But, I couldn't find the path between Pacman and food. For simplicity, I reversed the stack into queue in the following code.</p>
  
  <pre><code>''' A Sample BFS Algorithm '''
  
  import pprint
  def bfs( r, c, pacman_r, pacman_c, food_r, food_c, grid):
  
      stack = [(pacman_r-1,pacman_c),(pacman_r,pacman_c-1),(pacman_r,pacman_c+1),(pacman_r+1,pacman_c)]
      queue = stack[::-1]
  
  
      visited = []
      path = []
  
      print 'The pacman start',grid[pacman_r][pacman_c]
      count = 0
      while grid[pacman_r][pacman_c] != '.':
  
          move = queue.pop()
  
          if move not in visited:
              visited.append(move)
              new_r, new_c  = move[0], move[1]
  
              if grid[new_r][new_c] == '-':
                  path.append((new_r,new_c))
                  print 'The path', (new_r, new_c)
  
                  pacman_r = new_r
                  pacman_c = new_c
                  new_stack = [(pacman_r-1,pacman_c),(pacman_r,pacman_c-1),(pacman_r,pacman_c+1),(pacman_r+1,pacman_c)]
                  new_queue = new_stack[::-1]
                  queue = new_queue + queue
                  count = count+1
  
  
              if grid[new_r][new_c] == '.':
                  print "The destination", (new_r, new_c)
                  pacman_r = new_r
                  pacman_c = new_c
                  count = count + 1
  
      print "Count", count
  
      return
  
  pacman_r = 3
  pacman_c = 9
  
  food_r = 5
  food_c = 1
  
  r = 7
  c = 20
  
  
  
  grid = ['%%%%%%%%%%%%%%%%%%%%', '%--------------%---%', '%-%%-%%-%%-%%-%%-%-%', '%--------P-------%-%', '%%%%%%%%%%%%%%%%%%-%', '%.-----------------%', '%%%%%%%%%%%%%%%%%%%%']
  
  bfs(r, c, pacman_r, pacman_c, food_r, food_c, grid)
  </code></pre>
  
  <p>My <code>pacman_bfs</code> is able to expand all nodes correctly. The output I am obtaining is</p>
  
  <pre><code>3 9
  3 8
  3 10
  3 7
  2 10
  3 11
  2 7
  3 6
  1 10
  3 12
  1 7
  3 5
  1 9
  1 11
  3 13
  1 6
  1 8
  3 4
  1 12
  2 13
  3 14
  1 5
  2 4
  3 3
  1 13
  3 15
  1 4
  3 2
  1 14
  3 16
  1 3
  3 1
  2 16
  1 2
  2 1
  1 16
  1 1
  1 17
  1 18
  2 18
  3 18
  4 18
  5 18
  5 17
  5 16
  5 15
  5 14
  5 13
  5 12
  5 11
  5 10
  5 9
  5 8
  5 7
  5 6
  5 5
  5 4
  5 3
  5 2
  5 1
  </code></pre>
  
  <p>But this the list of expanded nodes. The path between the Pacman denoted by <code>"P"</code> and food <code>'.'</code> is </p>
  
  <pre><code>3 9
  3 10
  3 11
  3 12
  3 13
  3 14
  3 15
  3 16
  2 16
  1 16
  1 17
  1 18
  2 18
  3 18
  4 18
  5 18
  5 17
  5 16
  5 15
  5 14
  5 13
  5 12
  5 11
  5 10
  5 9
  5 8
  5 7
  5 6
  5 5
  5 4
  5 3
  5 2
  5 1
  </code></pre>
  
  <p>The total path is <code>32</code>. I don't know where I am having problem.</p>