C++

Forum

 
solving maze

marcopolo12 (5)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
 
 

I am try to generate a solution to a maze using a linked list implementation of a stack in some way. The maze is read in from a .txt file and consists of 1's for open spaces and 0's for walls. 

is the algorithm:

push the starting position onto the stack.
while the stack is not empty
   {
   pop the stack to get the current position.
   mark the current position as visited
   if the current position is the goal
      print the solution and exit the program.
   for each of four possible neighboring cells
      if the neighboring position is within the bounds of maze
         AND the neighboring position has not been visited
         then push the neighboring position onto the stack
   }
print "The maze has no solution";


can some one help with a good explication, I know this algorithm solving part go to maze.cpp at the end.
 
is what i have in therms of program:


[code]

#ifndef MAZE_H
#define MAZE_H

#include <fstream>     // for ifstream
#include <vector>      // for the maze[][] and visited arrays
using namespace std;


class Maze
   {
   public:
      Maze( ifstream &infile );
      void solve();
	  // void printSol(Position *p);
   private:
      int rows;    // the number or rows in the maze
      int cols;    // the number of columns in the maze

      vector< vector<int> > maze;       // 2-D dynamic maze array
      vector< vector<bool> > visited;   // the visited marks

      class Position  // the class for a position in the maze
         {
         public:
            Position( int r, int c, Position *p );
            int row;
            int col;
            Position* previous;
         };
   };
#endif


--------------------testMaze.cpp-------------------------------------------


/* short program to test the maze class.  All it does is read in the command
   line arguments. open the file. and call the maze constructor to build the
   maze according to the input file and call the solve() function to solve it.
*/
#include "Maze.h"
#include <iostream>
#include <cstdlib>


int main( int argc, char *argv[] )
   {
   if (argc != 2)  // make sure that the correct number of arguments were passed
      {
      cerr << "Usage: " << argv[0] << " <filename> " << endl;
      return 1;
      }

   ifstream infile;
   infile.open( argv[1] );   // open the input file

   if (! infile.is_open()) {
      cerr << "ERROR: could not open file " << argv[1] << endl;
      exit(1);
      }

   Maze maze( infile );    // build the maze
   maze.solve();           // solve the maze

   return 0;
   }


--------------------Maze.cpp----------------------------------

#include "Maze.h"
#include "Stack.h"
#include <iostream>
#include <iomanip>
#include <cstdlib>



// Position constructor initializes a position according to the passed in args
//
Maze::Position::Position( int r, int c, Position *p )
   {
   row = r;
   col = c;
   previous = p;
   }



// The maze constructor reads in and builds the maze representation
//
Maze::Maze( ifstream &infile )
   {
   infile >> rows >> cols;   // read in the size of the maze

   // set up the 2-D dynamic arrays: maze[][] and visited[][]
   // -------------------------------------------------------
   maze.resize( rows );
   visited.resize( rows );
   for (int i = 0; i < rows; i++)
      {
      maze[i].resize( cols );
      visited[i].resize( cols );
      }

   // read in the maze
   // ----------------
   for (int i = 0; i < rows; i++)
      for (int j = 0; j < cols; j++)
         {
         infile >> maze[i][j];

         if (maze[i][j] == 0)   
            visited[i][j] = true;    // mark walls visited so we don't go there
         else
            visited[i][j] = false;   // initialize all locations to unvisited
         }

   infile.close();
   }
Last edited on
marcopolo12 (5)
can some one help me on this please
fabtasticwill (218)
Could you please use code tags, it would be easier to read.
Smac89 (1727)
marcopolo12 (5)
fabtasticwill i did all ready use code tags can you look on it?
fabtasticwill (218)
They're showing up now. Don't know why it wasn't before.
jasonwynn10 (412)
that is an output tag not a code tag... code tags are in color.
Topic archived. No new replies allowed.