title: Breadth First Search falling one index short of desired outcome
body: <p>I'm trying to implement a bread-first search algorithm in Python to find the shortest path from the top left corner of a matrix (2d list) and the number 9, wherever it may fall in the matrix. For some reason when I run the code below with the included print statements, my x coordinate will outcome correctly (reached index 5 against desired 5). However, my y coordinate continues to be one index short (e.g. need 7 and it stops at 6). Additionally, when I print the queue, it's not empty but for some reason the function still ends. So, I don't understand why the code is exiting if neither criteria has been met (i.e. queue is empty or our desired coordinates have been found).</p>
  <pre><code>import numpy as np
  from collections import deque
  
  
  def shortest_path(maze):
      num_rows = len(maze)
      num_cols = len(maze[0])
  
  row_moves = [1, -1, 0, 0]
  col_moves = [0, 0, 1, -1]
  
  # Convert maze to an array and use numpy to find coordinates of our goal, which is the 9.
  maze_to_matrix = np.array(maze)
  destination = np.where(maze_to_matrix == 9)
  destination_x, destination_y = destination[1][0], destination[0][0]
  
  def is_valid_move(matrix, visited, y, x):
      return (y &gt;= 0) and (y &lt; num_rows) and (x &gt;= 0) and (x &lt; num_cols) \
             and matrix[y][x] == 1 and not visited[y][x]
  
  
  def bfs(matrix, dest_y, dest_x):
  
      # Construct matrix to keep track of visited cells.
      visited = [[False for x in range(num_cols)] for y in range(num_rows)]
  
      # Mark our origin as visited.
      # Our origin is always the top left node.
      visited[0][0] = True
  
      # Create an empty queue to keep track of our nodes to visit.
      queue = deque()
  
      # Append our starting coordinates and its minimum distance from the source to our queue.
      # First number is y coordinate, or outer list index.
      # Second number is x coordinate, or inner list index.
      queue.append((0, 0, 0))
  
      # Store the length of the longest path from source to destination
      min_dist = float('inf')
  
      # Pull most recently visited node off queue and determine if neighbouring
      # nodes are accessible. Continue until no valid unvisited nodes remain.
      while queue:
          (y, x, dist) = queue.popleft()
          print(f'y: {y} and dest_y: {dest_y}')
          print(f'x: {x} and dest_x: {dest_x}')
  
          # If our destination is found then break the loop and return value.
          if y == dest_y and x == dest_x:
              min_dist = dist
              break
  
          # Check for all possible movement directions from current (x, y)
          # and add valid movements to our queue.
          for i in range(4):
              if is_valid_move(matrix, visited, y + row_moves[i], x + col_moves[i]):
                  visited[y + row_moves[i]][x + col_moves[i]] = True
                  queue.append((y + row_moves[i], x + col_moves[i], dist + 1))
                  print(queue)
  
      if min_dist != float('inf'):
          return min_dist
      else:
          return &quot;Desired destination can't be reached from given origin points.&quot;
  
  return bfs(maze, destination_y, destination_x)
  
  
  maze = [
      [1, 0, 0, 0, 0, 0, 0],
      [1, 1, 1, 1, 0, 1, 0],
      [0, 1, 0, 1, 0, 1, 0],
      [1, 1, 0, 1, 1, 1, 0],
      [1, 0, 0, 0, 0, 1, 0],
      [1, 1, 1, 1, 0, 1, 0],
      [0, 0, 0, 1, 0, 1, 0],
      [0, 0, 0, 0, 1, 9, 0]
  ]
  
  print(shortest_path(maze))
  
  # Outputting y: 6 and dest_y: 7 x: 5 and dest_x: 5 and the queue is full.
  </code></pre>