# shortest path from start to end in a grid but with a twist

i am trying to solve a graph based problem , this is the statement: i have to find shortest route from position marked (s) to position marked (S) [Note : i marked S and E just for ease of understanding]. here is the catch in problem i can go only through cells marked 0 and cells marked 1 represents walls which are impassable.also i have the option to remove only one wall if it fetches me a shorter route to exit. Moves can only be made in cardinal directions; no diagonal moves are allowed.

sample 2d grid:

[
[0(S) 1  1  1  1   ],
[0    0  1  1  1   ],
[1    0  1  0  1   ],
[1    1  0  0  0(E)],
]


if the option of removing walls were not present i could usebfs or dijkstra to find the shortest route. this question has been asked here: here - they use full exhaustive search which is very bad for large matrices and they focus on language based optimisations which is not a good approach to a problem.

someone asked it here - the accepted answer has the following approach to it:

• Run a breadth-first search starting at the prison door, to find the distance of each passable space from the prison door.

• Run another breadth-first search starting at the escape pod, to find the distanceof each passable space from the escape pod.

• Now iterate over the walls, and consider removing each wall in turn. You know the distance of each passable space from the prison door and the escape pod, so you can immediately work out the length of the shortest route that passes through the space left by the wall
you just removed.

but i am not clear what does this(so you can immediately work out the length of the shortest route that passes through the space left by the wall ) mean in 3rd step above.

also is there any better way to approach it?

Use any search algorithm, where your state space is the set of tuples $(x,y,d)$ where $(x,y)$ are your co-ordinates and $d$ is a Boolean flag that says whether or not you've already dug through a wall. If $d=\mathrm{true}$, then your available moves are just to move to a vacant adjacent square; if $d=\mathrm{false}$, then your available moves are to move to a vacant adjacent square, or to move into a wall and set $d\leftarrow\mathrm{true}$.