Ask Question, Ask an Expert

+1-415-315-9853

info@mywordsolution.com

Ask Programming Language Expert

Introduction

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

1 loops the greatest and the least- write a program with a

1. Loops: The greatest and the least- Write a program with a loop that lets the user to enter a series of integers. The use should enter -99 to signal the end of the series. After all the numbers have been entered, the p ...

You must do this assignment correctly as described

You must do this assignment correctly as described below.  If you do not follow the directions or break the rules you will receive a 0 score. Simulation of checking tic-tac-toe board for wins by counting X and O in rows, ...

Computerscienceprogram-writeallofthefollowingmainprogramcall

Computer Science Program- Write all of the following: main program: Call a function to open an input file. Call a function to read 3 integers in from the input file. Call a function that will find 3 normalized doubles, g ...

1 implement dfs by using prolog2 implement bfs by using

1. Implement DFS by using PROLOG. 2. Implement BFS by using PROLOG. 3.  Solve the problem of Question 3 in Assignment 1 by using your PROLOG programs of DFS and BFS, respectively. Question 3 from Assignment 1 to Solve wi ...

Concurrent programming task ydetailsmany banking systems

CONCURRENT PROGRAMMING TASK YDETAILS Many banking systems allow multiple cardholders access a single account (e.g. a business account). The consequence of this is that is possible for more than one person to attempt to w ...

Purposethe purpose of this assignment is to practice using

Purpose: The purpose of this assignment is to practice using loops, selections, and other basic features of Java in order to solve a real-world problem. Program Description: The Jeddah Broker Company is one of the compan ...

Programming assignment- implement a udp client and udp

PROGRAMMING ASSIGNMENT- Implement a UDP client and UDP server that support simple timeout-based retransmission with AIMD congestion control: -The client should send as many packets as are in its CURWIN (current window) a ...

Electrical engineering computer methods assignmentq1 write

Electrical Engineering Computer Methods Assignment Q1. Write a program that given the following array, reverses all array elements and then prints them. int x[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; Q2. Write a program to d ...

Part a-1 what arguments can you make for the idea of a

Part A- 1. What arguments can you make for the idea of a single programming language for all programming domains? It would be ideal to have a single programming language for all 2. What arguments can you make against the ...

The briefyour small development team of ideally three

The Brief Your small development team of (ideally) three people has been asked to implement and test the Human Resource Information System desktop application. Your software product will be a database- backed desktop app ...

  • 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

A cola-dispensing machine is set to dispense 9 ounces of

A cola-dispensing machine is set to dispense 9 ounces of cola per cup, with a standard deviation of 1.0 ounce. The manuf

What is marketingbullwhat is marketing think back to your

What is Marketing? • "What is marketing"? Think back to your impressions before you started this class versus how you

Question -your client david smith runs a small it

QUESTION - Your client, David Smith runs a small IT consulting business specialising in computer software and techno

Inspection of a random sample of 22 aircraft showed that 15

Inspection of a random sample of 22 aircraft showed that 15 needed repairs to fix a wiring problem that might compromise

Effective hrmquestionhow can an effective hrm system help

Effective HRM Question How can an effective HRM system help facilitate the achievement of an organization's strate