C++ maze, have no clue how to solve it
You can view a maze as a two-dimensional table in which some elements are blank (representing a pathway) and some have asterisks in them (representing walls). An example of such a maze is shown on the left below. The goal in this maze is to find a path from the upper left corner of a maze to the bottom right corner. This path is shown below on the right, using periods to mark the path. The goal of the program you are about to write is to take a maze like that shown on the left and to find and mark a path through it like shown on the right.
Part I
Use a 2-dimensional array of chars to represent the maze. Read the maze from a file named maze.txt. There are some examples mazes in the assignment drop box.
This file has two numbers on its first line giving the number of rows and columns in the maze that it contains. The remaining lines contain the maze as shown above on the left. This maze has 30 rows and 30 columns. However, your program should work for any maze up to 100 rows and 100 columns. Assume that the first line of the maze.txt file will always contain the number of rows and columns in the maze.
The program should always begin in the upper left corner (i.e., element [1][1]). The goal is always to find a path to the bottom right corner (i.e., [next to last row][next to last column]). Mark the path with periods as shown in the maze on the right above.
To find the path through the maze you will need to keep track of where you currently are in the maze. You will need two variables to do this, say row and col. These two variables are both initialized to 1 to start. Repeat the following steps until row is the next to last row in the maze and col is the next to last column.
• Look right, then up, then left, then down, until you find an adjacent blank element to which to move. If you find such an element, put a period at the current element in the maze to mark the path and then move to the adjacent blank element next to the current one.
• If you didn't find any adjacent blank elements, then you are stuck in a dead end. Put an X in this element to mark that it is no good. Then look right, then up, then left, then down, until you find an element with a period in it. This must be the element that you were in before coming to this dead end. Move back to this adjacent element with the period in it.
• Now repeat these steps for the new element to which you just moved.
As long as the maze does not have a cycle (i.e., a path cannot loop back on itself), this algorithm will always find a path through the maze. Your program needs to work only for mazes with no cycles.
You should have at least four functions in your program. One function should read the maze into a 2-dimensional array from the file maze.txt. A second function should implement the algorithm above to find and mark a path through the maze. The third function should print the solved maze to the display screen. The fourth function is the main function. Note that the algorithm above marks the path with periods but also leaves many elements in the array with an X in them. Hence, when you display the final maze, replace all elements containing an X with a blank. This is how the display of the path through the maze on the right above was created.
Note that the function that reads the maze will have to pass the number or rows and columns by reference since this information must get back to the main function so that it can be passed along to the function that finds the path. The file from which you read the maze should be declared and opened inside the read function. Note that the read function will need to use the get operator to read the maze since you must read it a character at a time.
Be careful how you read the maze from the file. Remember that the beginning of the file contains two numbers. Use the >> operator to read these numbers. The rest of the file contains the maze itself. However, after the numbers and before the maze there are the End-Of-Line characters (one character in VC++, two characters in g++). To read the maze correctly, you will need to use the get operator to read this character or characters before you start reading the maze.
Use a while-loop read template to repeatedly ask the user if there is another maze to solve. The user will answer with a y or n. If the user enters y (or Y), ask for the filename that contains the maze, solve the maze, and write the maze solution to the display screen as described above. If the user enters n (or N), terminate the program.
Part I
Use a 2-dimensional array of chars to represent the maze. Read the maze from a file named maze.txt. There are some examples mazes in the assignment drop box.
This file has two numbers on its first line giving the number of rows and columns in the maze that it contains. The remaining lines contain the maze as shown above on the left. This maze has 30 rows and 30 columns. However, your program should work for any maze up to 100 rows and 100 columns. Assume that the first line of the maze.txt file will always contain the number of rows and columns in the maze.
The program should always begin in the upper left corner (i.e., element [1][1]). The goal is always to find a path to the bottom right corner (i.e., [next to last row][next to last column]). Mark the path with periods as shown in the maze on the right above.
To find the path through the maze you will need to keep track of where you currently are in the maze. You will need two variables to do this, say row and col. These two variables are both initialized to 1 to start. Repeat the following steps until row is the next to last row in the maze and col is the next to last column.
• Look right, then up, then left, then down, until you find an adjacent blank element to which to move. If you find such an element, put a period at the current element in the maze to mark the path and then move to the adjacent blank element next to the current one.
• If you didn't find any adjacent blank elements, then you are stuck in a dead end. Put an X in this element to mark that it is no good. Then look right, then up, then left, then down, until you find an element with a period in it. This must be the element that you were in before coming to this dead end. Move back to this adjacent element with the period in it.
• Now repeat these steps for the new element to which you just moved.
As long as the maze does not have a cycle (i.e., a path cannot loop back on itself), this algorithm will always find a path through the maze. Your program needs to work only for mazes with no cycles.
You should have at least four functions in your program. One function should read the maze into a 2-dimensional array from the file maze.txt. A second function should implement the algorithm above to find and mark a path through the maze. The third function should print the solved maze to the display screen. The fourth function is the main function. Note that the algorithm above marks the path with periods but also leaves many elements in the array with an X in them. Hence, when you display the final maze, replace all elements containing an X with a blank. This is how the display of the path through the maze on the right above was created.
Note that the function that reads the maze will have to pass the number or rows and columns by reference since this information must get back to the main function so that it can be passed along to the function that finds the path. The file from which you read the maze should be declared and opened inside the read function. Note that the read function will need to use the get operator to read the maze since you must read it a character at a time.
Be careful how you read the maze from the file. Remember that the beginning of the file contains two numbers. Use the >> operator to read these numbers. The rest of the file contains the maze itself. However, after the numbers and before the maze there are the End-Of-Line characters (one character in VC++, two characters in g++). To read the maze correctly, you will need to use the get operator to read this character or characters before you start reading the maze.
Use a while-loop read template to repeatedly ask the user if there is another maze to solve. The user will answer with a y or n. If the user enters y (or Y), ask for the filename that contains the maze, solve the maze, and write the maze solution to the display screen as described above. If the user enters n (or N), terminate the program.
Topic archived. No new replies allowed.