Consider the algorithm for traversing a maze from Section 15.6.4 Assume that we
ID: 3602193 • Letter: C
Question
Consider the algorithm for traversing a maze from Section 15.6.4 Assume that we start at position A and push in the order West, South, East, and North. In which order will the lettered locations of the sample maze be visited?
Here is the algorithm:
Push all paths from the point on which you are standing on a stack. While the stack is not empty Pop a path from the stack. Follow the path until you reach an exit, intersection, or dead end. If you found an exit Congratulations! Else if you found an intersection Push all paths meeting at the intersection, except the current one, onto the stack.
714 Chapter 15 The Java Collections Framework R15.25 Consider the algorithm for traversing a maze from Section 15.6.4 Assume that we start at position A and push in the order West, South, East, and North. In which order will the lettered locations of the sample maze be visited? O P M N D E ·RI 5.26 Repeat Exercise R15.25, using a queue instead ofa stack.Explanation / Answer
We will start from Point A
<A>
Pop from stack and Go to point A
insert B, because there is no west or south or north way
<B>
pop from stack and go to point B
Now We will first push C(East) and then H(north)
<C, H>
So now H will be popped and we will push G(West), I(East)and P(North) in order
<C, G, I, P>
Popped P now, we will push O(West), Q(East)
<C, G, I, O, Q>
Pop Q, Push J(South) and R(East) to stack
<C, G, I, O, J, R>
Pop R, it is a dead end so remove it..
<C, G, I, O, J>
Pop J, push K to stack
<C, G, I, O, J, K>
Pop K, It is a exit.. Congratulations.. We found it..