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:
Quote:
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:Quote:
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;
}
