You can use a backtracking approach. Your position is X,Y. 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)
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.
You can use a backtracking approach.
ReplyDeleteYour position is X,Y.
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
A kind of DFS:
ReplyDeleteStack 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.