Ask Question, Ask an Expert


Ask Programming Language Expert


In this assignment you need to simulate a maze traversal using so called recursive backtracking (the algorithm is given below).

The grid of #s and 0s in the following Figure is a two-dimensional array representation of a maze. #s represent the walls of the maze, and the zeros represent locations in possible paths through the maze. In the maze, you can move one step at a time in the four directions: up, down, right, left, no “diagonal” moves are allowed. A move can be made only to the location in the array which contains a zero.

# # # # # # # # # # # #
# 0 0 0 # 0 0 0 0 0 0 #
0 0 # 0 # 0 # # # # 0 #
# # # 0 # 0 0 0 0 # 0 #
# 0 0 0 0 # # # 0 # 0 0
# # # # 0 # 0 # 0 # 0 #
# 0 0 # 0 # 0 # 0 # 0 #
# # 0 # 0 # 0 # 0 # 0 #
# 0 0 0 0 0 0 0 0 # 0 #
# # # # # # 0 # # # 0 #
# 0 0 0 0 0 0 # 0 0 0 #
# # # # # # # # # # # #

prepare the recursive function called mazeTraversal, to walk through the maze like the one shown above.

Function mazeTraversal must attempt to locate the exit; it must also place the character 'x' in each square in the path.

In mazeTraversal you need to implement the following recursive algorithm:

• From the current location in the maze, try to move one space in one of the four directions (down, right, up or left).
• If it is possible to move in at least one direction, call mazeTraversal recursively, passing the new location in the maze as the current location.
• If it is not possible to go in any direction, return to the previous location in the maze and try new direction from that location

This recursive algorithm finds the exit (assuming there is an exit). If there is no exit, you will arrive at the starting location again.
Program the function to display the maze after each move so that the user can see how the maze is solved. The final output of the maze must display the path that solves the maze.

1) Class Maze. The Maze class must have:

a) Two private instance variables – int size, char **maze;
b) Constructor “Maze(char **c, int size)” – takes as an argument an n-by-n two-dimensional character array which contains only #s and 0s.
c) Public function void mazeTraversal(int a, int b)” – tries to “solve” the maze. Parameters a, b represent the entry point to the maze. Recursive algorithm for the mazeTraversal is described in the previous section.
d) friend ostream &operator<<(ostream &stream, Maze &m) – to print maze m in a tabular format.
e) Private function void mazeGenerator()” – randomly creates an n-by-n (3010≤≤n) Maze object which has an entry point on the left side. The algorithm for mazeGenerator should be as follows:

• You start with 2-dimensional n-by-n array maze containing only #s, and then you “dig” your way through it until reaching a border, marking the visited cells with 0s.
• The entry point is maze[n/2][0]
• First move is to the right, after that you chose randomly any of four possible directions to move.
• The function stops when it reaches a border.

f) Default constructor Maze() – calls the mazeGenerator.

2) main() function.

In the main function you must create three Maze objects:

• One on the figure in the section 0.
• A 12-by-12 maze that has an entry point but does not have an exit. You should design it yourself.
• A randomly generated maze object
Then the mazeTraversal function must be called on each of the created objects.

Programming Language, Programming

  • Category:- Programming Language
  • Reference No.:- M9681

Have any Question? 

Related Questions in Programming Language

Assignmentstep 1create a class named account with data

Assignment Step 1: Create a class named Account with data fields for an account number, payment amount and balance as well as the appropriate set and get methods. Include a constructor method that contains no arguments. ...

James wants to buy a motorcycleinstructions the following

James wants to buy a motorcycle Instructions: The following programming problem can be solved by a program that performs three basic tasks-Input Data, Process Data, and Output Results. Use RAPTOR to design a suitable pro ...

Assignment- computer applications for businesslearning

Assignment- Computer Applications for Business Learning Objectives: This assignment is designed to practice: 1. Basic understanding of JavaScript variables, including; a The declaration, initialization and assignment pro ...

Programming languages assignment write the following as

Programming Languages Assignment Write the following as Prolog rules:  1. Implement a rule "dogEnthusiast". Someone is a "dogEnthusiast" if they own AT LEAST TWO dogs. Assume that the only types of facts available are: " ...

Write a program that creates a picture of a mountain

Write a program that creates a picture of a mountain panorama from a height profile entered by the user. The following screenshot shows what the output could look like: The picture shall consist of 5 text lines of length ...

Program assignment multi-threaded programming in java

Program Assignment: Multi-threaded Programming in Java Using Locks Objectives: To practice programming cooperating, synchronized multiple threads of execution. Description: In this programming assignment you will simulat ...

A theater-seating chart is implemented as a two-dimensional

A theater-seating chart is implemented as a two-dimensional array of ticket prices, like this: ROW 6: 10 10 10 10 10 10 10 10 10 10 ROW 5: 10 10 10 20 20 20 20 10 10 10 ROW 4: 20 20 20 20 20 20 20 20 20 20 ROW 3: 20 20 3 ...

A certain loop requires 5 loads 7 stores and 8 arithmetic

A certain loop requires 5 loads, 7 stores, and 8 arithmetic operations. What is the minimum initiation interval for a software pipelining of this loop on a machine that executes each operation in one clock tick, and has ...

Design and implement your own simple class to represent any

Design and implement your own simple class to represent any household item of your choice (toaster, fan, hair dryer, piano ...) Your class should have a constructor, one additional method and at least one member variable ...

Create a class rectangle with attributes length and width

Create a class Rectangle with attributes length and width, each of which defaults to 1. Provide methods that calculate the rectangle's perimeter and area. It has set and get methods for both length and width. The set met ...

  • 4,153,160 Questions Asked
  • 13,132 Experts
  • 2,558,936 Questions Answered

Ask Experts for help!!

Looking for Assignment Help?

Start excelling in your Courses, Get help with Assignment

Write us your full requirement for evaluation and you will receive response within 20 minutes turnaround time.

Ask Now Help with Problems, Get a Best Answer

WalMart Identification of theory and critical discussion

Drawing on the prescribed text and/or relevant academic literature, produce a paper which discusses the nature of group

Section onea in an atwood machine suppose two objects of

SECTION ONE (a) In an Atwood Machine, suppose two objects of unequal mass are hung vertically over a frictionless

Part 1you work in hr for a company that operates a factory

Part 1: You work in HR for a company that operates a factory manufacturing fiberglass. There are several hundred empl

Details on advanced accounting paperthis paper is intended

DETAILS ON ADVANCED ACCOUNTING PAPER This paper is intended for students to apply the theoretical knowledge around ac

Create a provider database and related reports and queries

Create a provider database and related reports and queries to capture contact information for potential PC component pro