0
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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}$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ what should i search for ? shortest path to all nodes or shortest path to only passable nodes or shortest path to exit? $\endgroup$
    – anekix
    Commented Apr 28, 2017 at 10:49
  • 1
    $\begingroup$ The initial state is the start location and you've not dug through any walls; the goal states are the end location where you either have or have not dug through a wall. It sounds like you're not familiar with searching through general state spaces: I suggest you look up any tutorial on search algorithms for that. I'm not going to provide pseudocode because it is completely standard and available in any textbook or tutorial on search algorithms. $\endgroup$
    – David Richerby
    Commented Apr 28, 2017 at 12:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.