FEDERATION UNIVERSITY SCHOOL OF ENGINEERING & INFORMATION TECHNOLOGY ITECH 7603 C ADVANCED PROGRAMMING SEMESTER 1, 2016 ASSIGNMENT 2. MAZE 20 MARKS 0.Introduction. In this assignment you are required to simulate a maze traversal, i.e. you need to develop a program that starts from some location in a maze, and searches it to locate an exit. The maze should be implemented as a two-dimensional array of characters, where #s represent walls of the maze, whitespace characters represent empty spaces in the maze through which one can walk. In the maze, you can move one step at a time in the following four directions: up, down, right, left — no "diagonal" moves are allowed. A move can be made only to a location in the array that contains a whitespace. 1 Figure_1. If there is an exit the program finds way out and displays the solution as described below. See Figure_2 and Figure_3. If there is no way out of the maze, the program should report that there is no solution. 2 Figure_2. One starts from the location in the maze. depicted by green x. Figure_3. A possible solution(output). 1.The implementation requirements. 1.1. A maze should be implemented as a 2-dimensional square (n✕n) array of characters. The only allowed characters in the array are: • '#' — denote walls of the maze; • ' ' — denote unvisited locations in the maze; • 'x' — denote visited locations, that are not yet "dead ends"; • 'd' — "dead ends", i.e. locations from which you cannot proceed further and should return back. Initially the array(maze) contains only '#'s and ' 's. 1.2. You will need to define a Location class to represent locations in the maze and a Stack class to store visited locations. 1.3. To solve a maze you need to implement the following (recursive) algorithm: (a)Start from some initial location in the maze that contains a whitespace, i.e. push it on the stack. Proceed to (b). (b)If the top location on the stack contains a whitespace, override it by 'x'. • if this location is an exit proceed to (e). • else proceed to (c). (c)Try one by one locations adjacent to the top location on the stack. (up, down, left, right). • push on stack the first one that contains a whitespace. Proceed to (b). • else, if none of the adjacent locations contain a whitespace, override the top location's character by 'd' and pop the stack. • if the stack is empty proceed to (d). • else proceed to (c). (d) Print "There is no solution", then exit. (e) Print the found solution in a nice format like the one on Figure_3, then exit. Note, that the solution path is contained in the stack. 3 2. The main function. In the main function you have to test your program against two different mazes: • The one from Figure_2 (with the specified initial position). Please note, that your program may output a different solution. • Design a maze n✕n, n > 10, and solve it. 4 Allocated Marks: See Course Description Due Date: See Course Description Please refer to the Course Description for information relating to late assignments and special consideration. Plagiarism: Please refer to the Course Description for information regarding Plagiarism. Assignment Submission: Assignments must be submitted by the due date and your assignment should be completed according to the General Guidelines for Presentation of Academic Work . The following criteria will be used when marking of your assignment: • successful compilation • successful completion the required tasks • adherence to the guidelines provided • quality of code that adheres to the programming standards for the Course; including: • comments and documentation 1. code layout 2. meaningful variable names You are required to provide the following documentation, contained in an appropriate folder: • a statement of what has been completed and acknowledgement of the names of all people (including other students and people outside of the university) who have assisted you and details on what parts of the assignment that they have assisted you with 3. a printed copy of your code (this may be included as an Appendix). Please include this because we can provide more feedback this way In addition to submitting a printed copy of your written report into your tutor's assignment box, you should also submit the following using Moodle: • an electronic copy of your code. Zip up the project itself and submit with the name .zip • a copy of your report (surnameStudentIDAssign1.doc) including program code. 5 ITECH 7603 ADVANCED PROGRAMMING SEMESTER 1, 2016 ASSIGNMENT 2. MAZE 20 MARKS Student ID: ___________________ Student Name:_______________________ Marks awarded/deducted based upon considerations outlined on previous page Tasks Marks class Location 2 class Stack 5 implementation of the algorithm 1.3 8 main function 5 Marks deducted for badly commented or badly written code -2 Total 20 + (-2) 6