Saturday, September 29, 2012

Exit a labyrinth

given a matrix of 0/1, where the 1s represent the walls of a labyrinth, find the exit

1. You can use a backtracking approach.
1) start moving around as a clock from X+1, Y+1 (X+1-Y+1, X+0-Y+1, X-1,Y+1, ...)
2) if you find 0 (free space) and it's not previous position then
2.1) save in a stack: current position, direction and previous position
2.2) change position and go to step 1)
3) if you find 1 (wall) to step 1)
4) if all possible position around are 1 or a previous position then
4.1) pop from the stack: current position, direction and previous position
4.2) go to step 1)

Fabio
fabioang@gmail.com

2. A kind of DFS:

Stack stack = new Stack(neigh(startPos));
visit(startPos);
while(!stack.isEmpty()) {
Position pos = stack.pop();
if (isExit(pos)) youFoundTheExit();
if (isWall(pos)) continue;
if(visited(pos) continue;
stack.pushAll(neigh(pos));
visit(pos);
}

The meaning of the helper functions should be clear enough. Neigh() returns the North,East,South,West positions respect the input one. If on the border, then only the positions falling into the matrix are returned.

A nice to have would be to the list of steps bringing to the exit from the start. That could be done by maintaining a separate list of positions. The challenge here is that during the backtracking steps we need to remove from this list all the positions that have been found in a deeper level of the BSF. This can achieved keeping track of the current BSF level and storing inside the Position object also the BSF level where that object has been generated. Using these two info the list update should be easy.