I have an assignment from my data structures course.We learn almost nothing about C++.But they gave that assignment,and said do it anyway.Many of my classmates have it done with money.But I wanna learn how to make this project by myself.I'm thinking about the structure for 5 days and nights.I wanna know why I use struct,for what and how can I implement the stack.My if statements are ready in my head.please give the first parts of the code to encourage me,and let me do it.here is the assignment:
ASSIGNMENT 1 - MAZE SOLVER
In this assignment, you are asked to write a program that will find a path through a maze.
Creating Maze
You need to prepare a text file which consists of your maze map. All our mazes will be two-dimensional arrays of n rows and n columns. Each row, column cell is either open, or blocked by an internal wall. From any open cell, you may move left, right, up, or down to an adjacent empty cell. To solve a maze, you must find a path of open cells from a given start cell to a specified end cell. By default, you should assume that the start cell is in position (0,0).
Below is a sample 6x6 maze with blue 1's indicating the location of walls and black 0's indicating open cells, 9’s indicating end cell:
(THIS IS A SAMPLE MAZE. DON’T USE IT FOR YOUR ASSIGNMENT)
START--> 0 0 0 0 0 0
1 1 1 1 0 1
1 0 0 0 0 1
1 0 1 1 1 1
1 0 1 0 0 0
1 0 0 0 1 9 <--END
A sample solution path from START to END is:
[(0,0),(0,1),(0,2),(0,3),(0,4), (1,4),(2,4),(2,3), (2,2),(2,1),(3,1), (4,1),(5,1),(5,2),(5,3),(4,3),(4,4), (4,5),(5,5)]
The red asterisks below show the path.
START--> * * * * * 0
1 1 1 1 * 1
1 * * * * 1
1 * 1 1 1 1
1 * 1 * * *
1 * * * 1 * <--END
Finding Paths
To find paths in the maze, you should use the following algorithm. Some details have been omitted and you will need to think about how to fill them in.
1. Initialize the search list with the start position (0,0).
2. while the search list is not empty
1. remove the next element from search list
2. if the next element is the end position (has value ‘9’), then you have found a path
3. otherwise, add any valid moves to a neighbor of this element to the search list, if you haven’t visit that neighbor yet. (Be careful on the borders of the maze!)
3. If list is empty, and no path was found, no path exists.
The search list will be implemented using a stack. The list will store Coord
structs. You will need to think about what to store in the Coord struct.
Here is a more detailed pseudocode you can use:
Push the starting coordinate (sr,sc) onto the coordinate stack and
update maze[sr][sc] to indicate that the algorithm has encountered
it (i.e., set maze[sr][sc] to have a value other than '0'. For examle ‘2’ ).
While the stack is not empty,
{ Pop the top coordinate off the stack. This gives you the current
(r,c) location that your algorithm is exploring.
If the current (r,c) coordinate has value of ‘9’,
then we've solved the maze so print the coordinate!
Check where you can move from the current cell:
If you can move NORTH and haven't encountered that cell yet,
then push the coordinate (r-1,c) onto the stack and update
maze[r-1][c] to indicate the algorithm has encountered it.
If you can move SOUTH and haven't encountered that cell yet,
then push the coordinate (r+1,c) onto the stack and update
maze[r+1][c] to indicate the algorithm has encountered it.
If you can move EAST and haven't encountered that cell yet,
then push the coordinate (r,c+1) onto the stack and update
maze[r][c+1] to indicate the algorithm has encountered it.
If you can move WEST and haven't encountered that cell yet,
then push the coordinate (r,c-1) onto the stack and update
maze[r][c-1] to indicate the algorithm has encountered it.
}
There was no solution, so print ‘Not solvable!’
Requirments
1. Create a text file which consists of your 8x8 maze map. You can use notepad to create it.
2. Write a C++ program to search for a path in the maze using a stack.
3. When your program finds the solution, it should display the coordinate of the END cell. If there is no solution, display a message that the maze is not solvable.
Submitting
Along with your C++ source code and maze.txt, you should send the executable file (EXE) and a text file named README.TXT
Your README should include a brief summary of your methods, results and any known problems/bugs in your code.
