C++

Forum

 
Solving rat in maze using DFS

truckboy98 (11)
Hello,
I am trying to represent a maze using two classes: Maze and Cell. A Maze object is a rectangular grid of cells i.e., a 2-dimensional array of Cell objects.

I am confused about my DFS algorithm if its right. Moreover, how can I print the path after finding the goal, do I need to store the previous coordinates for it?

Maze example:

+---+---+---+---+---+
| |
+ + + +---+---+
| | | |
+ +---+---+---+ +
| | |
+ + +---+---+ +
| | |
+---+---+ +---+---+
|
+---+---+---+---+---+

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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
 
 #define _CRT_SECURE_NO_WARNINGS
    #include <iostream>
    #include<fstream>
    #include<string>
    #include <stack>
    using namespace std;
    
    class cell
    {
    private:
        bool visited;
        bool up, down, right, left;
        int x, y;
        int px, py;
        char status;
    public:
        cell() {
            up = down = right = left = 0;
            x = y = 0;
            status = ' ';
        }
        bool getUp() { return up; }
        bool getDown() { return down; }
        bool getRight() { return right;  }
        bool getLeft() { return left; }
        bool getvisited() { return visited; }
        void setUp(bool b) { up = b; }
        void setDown(bool b) { down = b; }
        void setRight(bool b) { right = b; }
        void setLeft(bool b) { left = b; }
    
        void setvisited(bool b=0) { visited = b; }
        void setstatus(char s = ' ') { status = s; }
        char getstatus() { return status; }
    
    };
    class Maze
    {
    private:
        int row, col;
        cell **arr;
    
    public:
        cell getcell(int r, int c){
            return arr[r][c];
        }
        void display();
    
        Maze(int r = 0, int c = 0)
        {
            this->row = r; this->col = c;
            arr = new cell*[row];
            for (int i = 0; i < row; i++)
                arr[i] = new cell[col];
        }
        int getrow()
        {
            return row;
        }
        int getcol()
        {
            return col;
        }
    
        void setgoal(int x, int y)
        {
            if (x > row || y > col||x < 0 || y < 0)
            {
                cout << "out of bounds " << endl;
                return;
            }
            arr[x][y].setstatus('G');
    
        }
        void setstart(int x, int y)
        {
            if (x > row || y > col||x < 0 || y < 0)
            {
                cout << "out of bounds " << endl;
                return;
            }
            arr[x][y].setstatus('S');
    
        }
    
    bool DFS(Maze m)
    {
        
        stack<cell> s;
        int x=0,y=0;
        s.push(arr[x][y]);
        cell current;
        while(!s.empty())
        {
            current = s.top();
            s.pop();
            if(current.getstatus()=='G')
            {
                return true;
            }
            if(!current.getvisited())
            {
                current.setvisited(true);
    
                if(current.getDown()&& (!arr[x+1][y].getvisited()))
                {
                        s.push(arr[x+1][y]); //how to check if visited
                }
                if(current.getUp()&&(!arr[x-1][y].getvisited()))
                {
    
                        s.push(arr[x-1][y]);
                }
                if(current.getLeft()&&(!arr[x][y-1].getvisited()))
                {
    
                        s.push(arr[x][y-1]);
                }
                if(current.getRight()&&(!arr[x][y+1].getvisited()))
                {
    
                        s.push(arr[x][y+1]);
                }
            }
            return false;
    
        }
    }
    };
    
    void Maze::display()
    {
        int i = 0, j;
        while (i < row) {
            j = 0;
            while (j < col) {
                cout << "+";
                if (arr[i][j].getUp())
                    cout << "---";
                else
                    cout << "   ";
                j++;
            }
            cout << "+\n";
            j = 0;
            while (j < col) {
                if (arr[i][j].getLeft())
                {
                    cout << "|";
                    cout << " " << arr[i][j].getstatus() << " ";
                }
                else
                {
                    cout << " ";
                    cout << " " << arr[i][j].getstatus() << " ";
                }
                j++;
            }
    
            if (arr[i][j - 1].getRight())
                cout << "|\n";
            else
                cout << " \n";
            i++;
        }
    
        j = 0;
        while (j < col)
        {
            cout << "+";
            if (arr[i - 1][j].getDown())
                cout << "---";
            else
                cout << "   ";
            j++;
        }
        cout << "+\n";
    }
Last edited on
truckboy98 (11)
Here is my main:
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
122
123
 

int main()
{
    int c ,r;
    ifstream in("maze.txt");
    char str1[100], str2[100], str3[100];
    in.getline(str1, 100);
    in.getline(str2, 100);
    in.getline(str3, 100);
    int line = 1, cell = 1;
    while (!in.eof())
    {
        cell = 1;
        cout << "line " << line << endl;
        int i = 0;
        bool top, down, right, left;
        top = down = right = left = false;
        int j = 0, k = 1;
        cout << "strlen = " << strlen(str1) << endl;
        while (i < strlen(str1) - 1)
        {
            top = down = right = left = false;
            if (str1[i] == '+') i++; //new cell

            if (str1[i] == '-')top = true;
            else if (str1[i] == ' ')top = false;
            i = i + 3; //wall above
            if (str2[j] == '|') left = true;
            else if (str2[j] == ' ')left = false;
            j = j + 4; //left wall
            if (str2[j] == '|') right = true;
            else if (str2[j] == ' ')right = false; //right wall
            if (str3[k] == ' ') down = false;
            else if (str3[k] == '-') down = true;
            k = k + 4; //wall below
            cout << "cell = " << cell << endl;
            cell++; c++; //cols
            cout << "Top :  " << top << "\t";
            cout << "down :  " << down << endl;
            cout << "right :  " << right << "\t";
            cout << "left :  " << left << endl;
            cout << endl << endl;

        }
        strcpy(str1, str3);
        cout << str1 << endl;
        in.getline(str2, 100);
        in.getline(str3, 100);
        cout << str2 << endl;
        cout << str3 << endl;
        line++; r++; //rows
    }
    Maze m(r, c);
    r = c = 0;
    while (!in.eof())
    {
        cell = 1;
        cout << "line " << line << endl;
        int i = 0;
        bool top, down, right, left;
        top = down = right = left = false;
        int j = 0, k = 1;
        cout << "strlen = " << strlen(str1) << endl;
        while (i < strlen(str1) - 1)
        {
            top = down = right = left = false;
            if (str1[i] == '+') i++; //new cell

            if (str1[i] == '-')
            {
                top = true;
                m.getcell(r,c).setUp(top);
            }
            else if (str1[i] == ' ') {
                top = false;
                m.getcell(r,c).setUp(top);
            }
            i = i + 3; //wall above
            if (str2[j] == '|')
            {
                left = true;
                m.getcell(r,c).setLeft(left);
            }
            else if (str2[j] == ' ') { left = false;
                m.getcell(r,c).setLeft(left);
            }
            j = j + 4; //left wall
            if (str2[j] == '|') { right = true;
                m.getcell(r,c).setRight(right);
            }
            else if (str2[j] == ' '){right = false; //right wall
                m.getcell(r,c).setRight(right);

            }
            if (str3[k] == ' ') { down = false; m.getcell(r,c).setDown(down); }
            else if (str3[k] == '-') { down = true;
                m.getcell(r,c).setDown(down);
            }
            k = k + 4; //wall below
            cout << "cell = " << cell << endl;
            cell++; c++; //cols
            cout << "Top :  " << top << "\t";
            cout << "down :  " << down << endl;
            cout << "right :  " << right << "\t";
            cout << "left :  " << left << endl;
            cout << endl << endl;

        }
        strcpy(str1, str3);
        cout << str1 << endl;
        in.getline(str2, 100);
        in.getline(str3, 100);
        cout << str2 << endl;
        cout << str3 << endl;
        line++; r++; //rows
    }
    if(m.DFS(m))
        cout<<" FOUND TARGET! "<<endl;
    else
        cout<<" DID NOT FIND TARGET! "<<endl;
        
    system("pause");
}
jonnin (11436)
that is a pretty good wall of code to work thru.
lets try talking first.
your standard maze search is something like recursion on this:
go north until you can't.
go east until you can't
go south until you can't
go west until you cant
been everywhere from here, done with this cell.

so it tries to go north, say it can (recursive push of this cell). tries again, it can (recursive push of cell). then maybe it can't, so it tries east, it can, but its a dead end, tries everything and can't, pop recursion, previous cell which now tries south....
but at the end of it all, your stack IS the answer, its right there.
you hit the solution square, and then pop the stack all the way back, and it will be the answer (in reverse, you can deal with that if you want it the other way around).

if you are doing it without recursion, then you have to track the answer manually, removing cells that did not lead to the exit as you go until only the right cells remain in the solution list.

does that make sense?
as a side note, your cells should maybe set visited to false in ctor so the loop to set all those can go away? Also use false for bool rather than zero is a little nicer looking.
Last edited on
truckboy98 (11)
Thanks a lot just got rid of the loop!

We are not allowed to use recursion for atm, so how is it possible to track it manually, and is my DFS algorithm correct?
jonnin (11436)
track it manually with a stack (you can use a vector as a stack, and I find that more flexible than the stl stack as you can do more things to it).
go to a node, you push it on the stack. then you try its directions. whichever way you go, you push each node you 'step on' to the stack. When you reach a dead end and go backwards to a previously vistited node, pop the bad one off. at the end when you reach your goal, same as before, the stack has the answer...

you are doing the same thing: recursion is just a fancy loop with a free/hidden stack structure. So looping with your own stack can do the same thing, just takes more code.

I can't tell if its right or not. The best way to figure this out is to make some small but somewhat complex mazes, run it, and look at the output. You can solve a maze at a glance nearly... should be clear if it got it right...
Last edited on
truckboy98 (11)
How about my way of reading the file i think its inefficient since at first time i read the file i count the rows and columns and then initialize it back again and reread it to set the cells
jonnin (11436)
do not worry about that right now. finish the rest of it cleanly.

you use cell and meant arr which should not compile. (57)
that aside,
you could over-allocate the arr array, instead of r and c pick some max size say 1000 and 1000, for example, and use as much as you want of it as you read the file, leave the other space unused, and read the file once. Another option would be to have the dimensions be the first entry in the file (r and c both) and read the file once using that.

later you will learn vector, which can grow to fit the data, making that ** aggravation go away (read file once, grow to fit). you will also learn about binary files which have fixed length for each chunk of data, making it easy to know how many you have (file size / chunk size = #) (read file once, got # of records efficiently).
Last edited on
truckboy98 (11)
I was asked to have a previous x and a previous y too, in order to print the path how is that possible i dont get it?
Topic archived. No new replies allowed.