Maze problem implemented using backtracking to find all paths and shortest paths from source to destination.
Maze problem requires finding a path from source to a destination in a matrix. A cell can have a value of either zero or one. We can only traverse along the cells with value zero in any four directions (up, down, left, right). We cannot traverse along the cells with value 1 nor diagonally. The cell with value S will be the starting point and the cell with value E will be the destination. Four different variations of this problem has been solved: path exists or not, find any given path, find all the paths, find all the shortest paths.
The solution utilized an iterative backtracking approach. Three main data structures were used: a stack to store the untraversed path, a queue to store the current traversed path and a stock where each entry in the stack stores a traversed path with a minimum score. No libraries like STL was utilized for data structures and all data structures was developed from scratch in C++.