My friends had an algorithm project: Finding a way to get out of a maze.
Maze is a 10×10 matrix, and 1 is wall, 0 is a route.
How can a program find the exit?
1. Easy way.
Create a temporary matrix(called array in programming), and record where the program has been.
When it needs to come back to it’s original place, the matrix is used.
Cons: If the matrix is huge, the program doubles its memory size.
2. Smart(efficient) way.
A browse() method visits all possible spots, and if needs to come back, it checks where it shouldn’t check.
For example, if a browse() method detected a way using “DOWN” and create another browse() method, this method cannot detect “UP” but ends there and return to original(parent) browse() method.
Pros: This prevents a browse() method to create a child method for back-tracking.
Uses much less memory space.