title: How do I find shortest path in maze with BFS?
body: <p>I am trying to find a way to solve a maze. My teacher said I have to use BFS as a way to learn. So I made the algorithm itself, but I don't understand how to get the shortest path out of it. I have looked at others their codes and they said that backtracking is the way to do it. How does this backtracking work and what do you backtrack?</p>
  
  <p>I will give my code just because I like some feedback to it and maybe I made some mistake:</p>
  
  <pre><code>def main(self, r, c):
      running = True
      self.queue.append((r, c))
      while running:
          if len(self.queue) &gt; 0:  
              self.current = self.queue[0]
              if self.maze[self.current[0] - 1][self.current[1]] == ' ' and not (self.current[0] - 1, self.current[1])\
                      in self.visited and not (self.current[0] - 1, self.current[1]) in self.queue:
                  self.queue.append((self.current[0] - 1, self.current[1]))
              elif self.maze[self.current[0] - 1][self.current[1]] == 'G':
                  return self.path
  
              if self.maze[self.current[0]][self.current[1] + 1] == ' ' and not (self.current[0], self.current[1] + 1) in self.visited\
                      and not (self.current[0], self.current[1] + 1) in self.queue:
                  self.queue.append((self.current[0], self.current[1] + 1))
              elif self.maze[self.current[0]][self.current[1] + 1] == 'G':
                  return self.path
  
              if self.maze[self.current[0] + 1][self.current[1]] == ' ' and not (self.current[0] + 1, self.current[1]) in self.visited\
                      and not (self.current[0] + 1, self.current[1]) in self.queue:
                  self.queue.append((self.current[0] + 1, self.current[1]))
              elif self.maze[self.current[0] + 1][self.current[1]] == 'G':
                  return self.path
  
              if self.maze[self.current[0]][self.current[1] - 1] == ' ' and not (self.current[0], self.current[1] - 1) in self.visited\
                      and not (self.current[0], self.current[1] - 1) in self.queue:
                  self.queue.append((self.current[0], self.current[1] - 1))
              elif self.maze[self.current[0]][self.current[1] - 1] == 'G':
                  return self.path
  
              self.visited.append((self.current[0], self.current[1]))
              del self.queue[0]
              self.path.append(self.queue[0])
  </code></pre>
  
  <p>As maze I use something like this:</p>
  
  <pre><code>############
  # S        #
  ##### ######
  #          #
  ######## ###
  #          #
  ## ##### ###
  #         G#
  ############
  </code></pre>
  
  <p>Which is stored in a matrix</p>
  
  <p>What I eventually want is just the shortest path inside a list as output.</p>