CSC231 Homework 12 Solutions 2012
--D. Thiebaut 15:01, 13 December 2012 (EST)
The solution of the program can be found here. Aurelia's original program was actually removing all the v characters at the end. I modified it so that it wouldn't, and asked you to figure out how to get the feature back. The simplest solution was to create a new function to print the maze without the v characters and call it at the very end of the program. Much simpler than modifying the rest of the program!
For the amount of stack, this is the way I see the program: when it lands in a new square of the maze, it puts a '.' (dot) there, and checks if the dot is actually on the periphery of the maze, in which case the stopping condition is met and the program back tracks back to the top level of the recursion indicating that the search was successful. If from the current position the recursive visit function cannot successfully go anywhere, it puts a 'v' in the square it's in, and returns to its caller. So the dots represent the state of the search, and for each dot we have a stack frame in the stack for the visit function. So the worst case, the deepest stack we can have is when the maze is full of dots:
......................... ......................... ......................... ......................... ......................... ......................... ......................... .........................
But actually, this isn't quite true, because any dot on the periphery of the maze corresponds to a successful exit from the maze, so for the dots to be bound inside the maze, we need to have walls:
######################### #.......................# #.......................# #.......................# #.......................# #.......................# #.......................# #########################
So the number of dots in the case is (width-2) * (height-2), and the stack depth can be at most O(width.height), or K1(width-2) * (height-2) + K2, where K1 and K2 represent the number of words visitMaze pushes in the stack before it recurses, and K2 represent the number of words pushed in the stack by the main program before calling the visitmaze, plus the maximum number of words visitmaze will add to the stack to print the maze. You can figure these numbers out! :-)
