title: How can I improve the speed of this shortest path/shortcut(array graph DS) solution?
body: <p>Given a maze as an array of arrays where 1 is a wall and 0 is a passable area:
  </p>
  
  <pre><code>Must include start node in distance, if you BFS this it will give you 21.
  
  [0][0] is the start point.
  
      |
  [   V
     [0, 0, 0, 0, 0, 0], 
     [1, 1, 1, 1, 1, 0], 
     [0, 0, 0, 0, 0, 0], 
     [0, 1, 1, 1, 1, 1], 
     [0, 1, 1, 1, 1, 1], 
     [0, 0, 0, 0, 0, 0]&lt;--   [-1][-1] is the end point.
  ]
  </code></pre>
  
  <p>We must find the shortest path possible, we can remove one '1' to help create a shortcut.</p>
  
  <p>The shortcut that creates the shortest path is changing [1][0] to 0, opening a path that makes the distance 11.</p>
  
  <pre><code>[
     [0, 0, 0, 0, 0, 0], 
  --&gt;[0, 1, 1, 1, 1, 0], 
     [0, 0, 0, 0, 0, 0], 
     [0, 1, 1, 1, 1, 1], 
     [0, 1, 1, 1, 1, 1], 
     [0, 0, 0, 0, 0, 0]
  ]
  return 11
  </code></pre>
  
  <p>My original thought process was run through every element and check if it's == 1, then do a bfs compare the distance with the min.</p>
  
  <p>But ofcourse that was too slow. So I thought running through every element and check if it's 1, then see if it has exactly two neighbors that are passable because that seems to the only possible case where a shortcut is meaningful.</p>
  
  <p>Here is my code:</p>
  
  <pre><code>import copy
  def bfs(maze):
      visited = set()
      queue = []
      mazeHeight = len(maze)
      mazeWidth = len(maze[0])
      queue.append(((0,0),1))
  
      while queue:
          yx,distance = queue.pop(0)
          y,x = yx
          visited.add(yx)
          if yx == (mazeHeight-1,mazeWidth-1):
              return distance
  
          if y+1 &lt; mazeHeight:
              if not maze[y+1][x] and (y+1,x) not in visited:
                  queue.append(((y+1,x),distance+1))
  
          if y-1 &gt;= 0:
              if not maze[y-1][x] and (y-1,x) not in visited:
                  queue.append(((y-1,x),distance+1))
  
          if x+1 &lt; mazeWidth:
              if not maze[y][x+1] and (y,x+1) not in visited:
                  queue.append(((y,x+1),distance+1))
  
          if x-1 &gt;= 0:
              if not maze[y][x-1] and (y,x-1) not in visited:
                  queue.append(((y,x-1),distance+1))
  
      return False
  
  def answer(maze):
      min = bfs(maze)
      mazeHeight = len(maze)
      mazeWidth = len(maze[0])
      for y in range(mazeHeight):
          for x in range(mazeWidth):
              if maze[y][x]:
                  oneNeighbors = 0
                  if y+1 &lt; mazeHeight:
                      if not maze[y+1][x]:
                          oneNeighbors += 1
  
                  if y-1 &gt;= 0:
                      if not maze[y-1][x]:
                          oneNeighbors += 1
  
                  if x+1 &lt; mazeWidth:
                      if not maze[y][x+1]:
                          oneNeighbors += 1
  
                  if x-1 &gt;= 0:
                      if not maze[y][x-1]:
                          oneNeighbors += 1
                  if oneNeighbors == 2:
                      tmpMaze = copy.deepcopy(maze)
                      tmpMaze[y][x] = 0
                      tmpMin = bfs(tmpMaze)
                      if tmpMin &lt; min:
                          min = tmpMin
  
      return min
  
  
  print(answer([[0, 0, 0, 0, 0, 0], [1, 1, 1, 1, 1, 0], [0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 1], [0, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0]]))
  </code></pre>
  
  <p>Any suggestions to improve the speed?</p>