Maze Solver

[RobGillespie]

I have a big problem here. I've worked through this thing and I just don't know where to go with this. They don't give me any information on the header file maze.h. I'm 100% lost. Here it is:

Write a program that finds an "economic" (non-repeating) path through a maze. You may assume that the header files maze.h (as defined below), p2stack.h and p2queue.h will be available to include. Submit your source file as maze.cpp.

Sample input files and program executions are shown below.

sample1.txt
5
XXXXX
XXSXX
XX.XX
XXFXX
XXXXX

Output:
sample1.txt
SS
Note that there is no prompt or other output, just reading the filename as input and displaying the discovered path.

sample2.txt
6
XXXXXX
XXSX.X
XX...X
XXFX.X
X....X
XXXXXX
For sample2.txt, either of these two solutions is acceptable:

sample2.txt
SS
sample2.txt
SEESSWWN
maze.h
The header file maze.h is available when you submit your maze solver and will contain functions meeting the following specifications:

/*************
* Data Types*
*************/
Path // a series of locations, steps taken through the maze
Location // one point in the maze

/*************
* Functions *
*************/
// Given an input stream (such as cin or a file input stream),
// read the maze layout and return the start Location
inputMaze(istream) -> Location

// Initialize Path P to contain just one location: L
initialize(Path P,Location L)

// Initialize Path P to be the same as Path C
initialize(Path P,Path C)

// Return true if Path is finished (has reached space F)
isFinished(Path) -> bool

// Return true if Location is a "good step" for the Path:
// if it is not a wall, not somewhere the path has already been
isGoodStep(Path,Location) -> bool

// Return the Location immediately north of (above) a given Location
// Similarly for west/east/south
northOf(Location) -> Location
{also southOf/eastOf/westOf}

// Add Location to the steps taken in the Path
takeStep(Path,Location)

// Return the Location where the Path has reached (the last step)
getCurrentLocation(Path) -> Location

// Display Path as series of directions (N,S,E,W)
// Use overloaded output operator
// For example, cout << p;
ostream& operator<< (ostream&,Path)

[helios]

What do you mean, they give you no information? They're telling you the types that are exposed and the operations that can be performed on those types. What more could you need?

[RobGillespie]

I meant it just wasn't enough for ME to understand what they were doing with those functions. He explained it in class today so I think I'm good. He explained it an I took notes, and made some pseudocode. Now I just have to translate it.

[RobGillespie]

I've gotten pretty far with this. Here is what I have so far:

#include <iostream>
#include <fstream>
#include "p2queue.h"
#include "maze.h"
using namespace std;

int main()
{
//Collect information from the file.
  ifstream fin;
  string filename;

  cin >> filename;

//Open the provided file.
  fin.open(filename.c_str());

Location start = inputMaze(fin); //Input the file and find starting location.

Queue<Path> options; //Declare options of type Queue.

//Prepare a path.
Path A;
initialize(A, start);

//Push starting location on to options.
push(options, A);
start = getCurrentLocation(A);

//Begin testing surrounding spots until 'options' is empty.
while( true )
{
  Path current_path;
  current_path = pop(options);

  //Test every direction and push good steps.
  if(isFinished(current_path))
  {
    push(options, current_path);
    break;
  }
  if(isGoodStep(current_path, northOf(start)))
  {
    Path B;
    initialize(current_path, B);
    takeStep(B, start);
    push(options, current_path);
  }
  if(isGoodStep(current_path, eastOf(start)))
  {
    Path B;
    initialize(current_path, B);
    takeStep(B, start);
    push(options, current_path);
  }
  if(isGoodStep(current_path, southOf(start)))
  {
    Path B;
    initialize(current_path, B);
    takeStep(B, start);
    push(options, current_path);
  }
  if(isGoodStep(current_path, westOf(start)))
  {
    Path B;
    initialize(current_path, B);
    takeStep(B, start);
    push(options, current_path);
  }
}
fin.close();

cout << pop(options);
}

I keep getting a segmentation fault for this code. I can't see why. Can someone help?