C++ "Maze" Assignment

Question

The mini-program is supposed to print out all the possible routes through a maze, where the entrance/starting point is always one down from the top left corner and all possible exits that are always on the right wall. It retrieves the maze from a text file.

The maze is actually just a bunch of text. The maze consists of an n x n grid, consisting of "#" symbols that are walls, and assorted letters [a...z] representing the walkable area/paths. Letters can repeat but can never be side by side.

The maze is 15x15.

An uppercase S always labels the entrance, and is on the left wall in the second highest spot. A possible path is only through letters- you can't walk on # symbols. Any letter on the right wall represents exit(s).

For example,

######
Sa#hln
#bdp##
##e#ko
#gfij#
######

is a possible maze. My little program is supposed to print out all the possible routes after reading the text file that actually contains the maze.

A call to the program would generate the following output to the screen:

Path 1: S,a,b,d,e,f,i,j,k,o
Path 2: S,a,b,d,p,h,l,n
2 total paths

How about would I go about doing this? I don't need a complete code answer, I just want some guidance on how to approach this problem.

So far I've done everything except the actual algorithm itself that recursively checks adajcent squares to see if you can walk on them, and I don't know how I'd work on multiple paths.

This is what I have so far (I know my pathcheck is wrong, but I didn't know what else to do):

    #include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <sstream>
#include <cstdio>
using namespace std;

ifstream file("maze.txt");
vector<char> vec(istreambuf_iterator<char>(file), (istreambuf_iterator<char>())); // Imports characters from file
vector<char> path;                      // Declares path as the vector storing the characters from the file
int x = 18;                             // Declaring x as 18 so I can use it with recursion below
char entrance = vec.at(16);             // 'S', the entrance to the maze
char firstsquare = vec.at(17);          // For the first walkable square next to the entrance
vector<char> visited;                   // Squares that we've walked over already

int main()
{
    if (file) {
        path.push_back(entrance);               // Store 'S', the entrance character, into vector 'path'
        path.push_back(firstsquare);            // Store the character of the square to the right of the entrance
                                                // into vector 'path'.

        while (isalpha(vec.at(x)))
        {
            path.push_back(vec.at(x));
            x++;
        }

        cout << "Path is: ";                    // Printing to screen the first part of our statement

        // This loop to print to the screen all the contents of the vector 'path'.
        for(vector<char>::const_iterator i = path.begin(); i != path.end(); ++i)  // 
        {
        std::cout << *i << ' ';
        }

        cout << endl;
        system ("pause");                       // Keeps the black box that pops up, open, so we can see results.
        return 0;
        }
}

Thanks!

What have you tried? Are you stuck on some aspect of your solution? Have you done the basics, such as reading the maze from a file into a data structure in your program? — Greg Hewgill
I'd use recursion with a list saving current state, and each recursion making 4 recursive calls for the next step. On each recursion check if the current location has already been visited, and if it's the end block. — user684934
I don't know how to do those, but they're great suggestions.. I'll try to look up how to read a text file first and then figure out the recursion part :) And yes, I can use recursion. — forthewinwin

Marvo Marvo · Accepted Answer · 2012-05-24T02:52:59

You need a few things to start:

A way of representing the maze in memory -- a "data structure" that's appropriate for a grid like a maze
Methods for accessing and manipulating that maze
A method of rendering the maze -- perhaps to print out a maze
A way of tracking your progress
An algorithm for solving the problem at hand

Consider starting with a much smaller maze -- perhaps one that's 3x3 in size -- with a path that goes straight across the map. Your program should be able to solve that. Then change the path to curve a bit. Then make the map bigger. Make the path harder. Have some "red herring" branches off the path.

A smaller map, increasing in complexity, should make debugging the effort a lot easier. (And if you don't know how to use a debugger, having a small problem to start will make learning the debugger easier.)

Good luck!

C++ "Maze" Assignment

5 Answers