I am new to backtracking problems and stumbled upon this maze problem. There are lots of solution to solve maze problem. But I was wondering about dead-end filling problem.
Is Dead-end filling algorithm to find output in a maze considered as a backtracking algorithm?
Viewed 1310
1 Answers
The first step of this algorithm is to find all dead-ends. To achieve this the algorithm will traverse through the maze like through a matrix and mark all floors with 3 walls, say by putting them onto a stack. So this loop clearly isn't backtracking.
The second step consists of filling up the dead-ends until a junction is met. This is done by fetching a dead-end from the stack and working along the corridor. Still no backtracking.
The final step is already the solution, a path from entry to exit. Traversing this, if needed, is trivial. So this algorithm is neither recursive nor backtracking.
Related