We all know the classic problem of a rat in a maze. It involves a
starting position, which is the place where the rat begins its journey;
to a specific destination, which will be only one position to reach the
other side of the maze.
This problem can be solved with a certain algorithm using stacks. Although there are infinite number of algorithms using stacks, this one is an idea of mine and any feedback or suggestions are always welcome.
THE IDEA:
Let us first represent the maze as a 2D matrix, that has m rows and n columns, so that its dimension can be represented as (m*n). The basic idea is simple. It relies on the idea of 0's and 1's that will be the only elements present in the matrix. 0 means there is a free path in that direction, and 1 means it is blocked. In order to avoid confusions at the terminal extremes of the matrix, a (m*n) matrix is represented as a matrix with (m+1) rows and (n+1) columns with, the boundaries carrying a 1 all over the actual maze matrix, so that the path won't get outside the matrix.
THE PRIORITY:
The path follows a certain priority of directions. It is as follows:
The free path movement is strictly restricted to follow this priority. Backtracking is also present in case of a wrong path chosen.
STACK IDEA:
The initial position is pushed into the stack. From now on, the positions are pushed in to the stack, where the rat moves. Thus, at any time, the stack_top returns the current position of the rat in the maze(matrix cell). In case of backtracking, if there are no paths left further more except the one path that we actually used to come in, stack is popped until there is another way than the older one.
These steps are repeated until the end position is reached. This is just a general idea of the implementation. The time complexity of this approach is O(n), depending on the number of paths available.
This problem can be solved with a certain algorithm using stacks. Although there are infinite number of algorithms using stacks, this one is an idea of mine and any feedback or suggestions are always welcome.
THE IDEA:
Let us first represent the maze as a 2D matrix, that has m rows and n columns, so that its dimension can be represented as (m*n). The basic idea is simple. It relies on the idea of 0's and 1's that will be the only elements present in the matrix. 0 means there is a free path in that direction, and 1 means it is blocked. In order to avoid confusions at the terminal extremes of the matrix, a (m*n) matrix is represented as a matrix with (m+1) rows and (n+1) columns with, the boundaries carrying a 1 all over the actual maze matrix, so that the path won't get outside the matrix.
THE PRIORITY:
The path follows a certain priority of directions. It is as follows:
- NORTH
- NORTH EAST
- EAST
- SOUTH EAST
- SOUTH
- SOUTH WEST
- WEST
- NORTH WEST
The free path movement is strictly restricted to follow this priority. Backtracking is also present in case of a wrong path chosen.
STACK IDEA:
The initial position is pushed into the stack. From now on, the positions are pushed in to the stack, where the rat moves. Thus, at any time, the stack_top returns the current position of the rat in the maze(matrix cell). In case of backtracking, if there are no paths left further more except the one path that we actually used to come in, stack is popped until there is another way than the older one.
These steps are repeated until the end position is reached. This is just a general idea of the implementation. The time complexity of this approach is O(n), depending on the number of paths available.
