How can I improve the speed of this shortest path/shortcut(array graph DS) solution?
<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>

<p>You seem to be on the right track. The following approach can be considered:</p>

<ol>
<li><p>Form a graph of <code>n x m</code> nodes where <code>n</code> and <code>m</code> are the dimensions of the maze matrix.</p></li>
<li><p>There is an edge of cost <strong>zero</strong> between two nodes if they are adjacent <code>0</code>s. There is an edge of cost <strong>one</strong> between two nodes if they are both <code>0</code>s separated by a <code>1</code>.</p></li>
</ol>

<p>(Note that there shall be two costs that you shall need to maintain for each path, one is the above <code>zero-one</code> cost and the other is the number of nodes in the path to keep track of the minimum).</p>

<ol start="3">
<li><p>Then perform BFS and consider only paths that have a <code>zero-one cost &lt;= 1</code>.</p></li>
<li><p>This shall give you a linear time algorithm (linear in number of nodes).</p></li>
</ol>

<p>Following code may contain bugs but it should get you started.</p>

<pre><code>def bfs(maze):
    visited = set()
    queue = []
    mazeHeight = len(maze)
    mazeWidth = len(maze[0])
    queue.append(((0,0),1,0))    

    while queue:
        yx,distance, cost = 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, cost))

        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, cost))

        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, cost))

        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, cost))

        if cost == 0:
            if y+2 &lt; mazeHeight:
                if not maze[y+2][x] and (y+2,x) not in visited and maze[y+1][x] == 1:
                    queue.append(((y+2,x),distance+2, cost+1))

            if y-1 &gt;= 0:
                if not maze[y-2][x] and (y-2,x) not in visited  and maze[y-1][x] == 1:
                    queue.append(((y-2,x),distance+2, cost+1))

            if x+1 &lt; mazeWidth:
                if not maze[y][x+2] and (y,x+2) not in visited and maze[y][x+1] == 1:
                    queue.append(((y,x+2),distance+2, cost+1))

            if x-1 &gt;= 0:
                if not maze[y][x-2] and (y,x-2) not in visited and maze[y][x-1] == 1:
                    queue.append(((y,x-2),distance+2, cost+1))

    return False
</code></pre>

python algorithm data-structures array-algorithms