Hello:
I already finished my program, but i cannot print out the result on the screen, and i think there have a few logical problems.
Here is the instruction:
Write a program to read a maze from a text file into your array, print the unsolved maze, solve the maze, and then print the solution. You may assume the maze will fit in a 24-row by 80-column array. The maze will be in a file with the number of rows and columns on the first line, followed by the lines defining the maze, with '*' representing a wall and ' ' (space) representing a corridor. For example, here is a small (8-by-12) maze (on my web site as maze8-12.txt):
8 12
**********
* * *
* ****** *
***** *
* ******
*** *** *
* ** *
**********
You may assume that the maze will always have a solution. The program is easily generalized to show if there is no solution, but this is not required for this assignment. For an n-by-m maze held in a char array a[n][m], the starting point (at the top left) is a[0][0], and the ending point (at the bottom right) is at a[n-1][m-1]. When you print the solved maze, show the path through the maze by marking all points in the solution set with '#'. For example, here is the same maze printed showing the solution:
##**********
*#*########*
*###******#*
*****######*
* ###******
***#***####*
* #####**#*
**********##
Notice, moves down "blind alleys" are left off the solution. I will discuss the algorithm for this in class, and you must use the recursive backtracking algorithm I give you for this program. This is not a large program- about two pages of code.Here is my code:8 12
**********
* * *
* ****** *
***** *
* ******
*** *** *
* ** *
**********
Code:#include <iostream> #include <fstream> #include <string> using namespace std; char map[24][80]; bool nnew[24][80]; int n, m; // print maze solution void print() { cout << endl << "Solution = " << endl; int i, j; for (i = 0; i < n; ++i, cout << endl) for (j = 0; j < m; ++j) cout << map[i][j]; exit(0); } void dfs(int i, int j) { // range coordinates check if (!(i >= 0 && i < n && j >= 0 && j < m)) return; // do not processing walls and earlier marked cells if (map[i][j] == '*' || nnew[i][j]) return; // memorize char of the map char ch = map[i][j]; // put in this cell segment of our future path map[i][j] = '#'; // marked cell, we only moved to the unmarked positions nnew[i][j] = 1; // yes! if (i == n - 1 && j == m - 1) print(); // process all 4 directions dfs(i - 1, j); dfs(i, j + 1); dfs(i + 1, j); dfs(i, j - 1); // restore map map[i][j] = ch; nnew[i][j] = 0; } int main() { ifstream cin("c:\maze8-12.txt"); cin >> n >> m; int i, j; string str; // ignore \n symbol cin.ignore(); for (i = 0; i < n; ++i) { // read string describing new row of the map getline(cin, str); for (j = 0; j < m; ++j) // construct current cell of the map map[i][j] = str[j]; cout << str << endl; } // recursive search from upper-left corner dfs(0, 0); return 0; }



LinkBack URL
About LinkBacks


