0

Anyone have any suggestions on how to tackle this algorithm? First off, I am going to say this is a homework assignment. Secondly, I am not asking for the answer. Rather, I am asking for guidance or a little head start. I did a google search and I found this helpful website https://www.cs.bu.edu/teaching/alg/maze/ . I am trying to replicate what they have to my code. So after the user enters the starting point, I should check to see if the I am allowed to move up, down, left, or right. Correct?

Screenshot: https://i.stack.imgur.com/JQoO2.jpg

so let's say the user enters 3 2 (row column) as starting position. It's going to heck up and see it is '+' which means closed. Then it's going to check right, which is 'O', so it is going to move there.

Any advice on the algorithm? Again, I am not asking for the solution. I am just asking for someone to guide me or just help me get started. Any help is appreciated. Thank you.

Main.cpp

    #include <fstream>
    #include <iostream>
    #include <string>
    #include "Maze.h"
    int main()
    {
      using namespace std;
      ifstream inFile;
      string fileName;
      int row, col;
      cout << "Enter file name" << endl;
      cin >> fileName;
      inFile.open(fileName.c_str());
      Maze maze(inFile);
      maze.Print();
      cout << "Enter row and col of starting position; " << endl<< "negative row stops the processing." << endl;
      cin >> row;
      while (row >= 0)
      {
        Maze anotherMaze = maze;
        cin >> col;
        if (anotherMaze.TryToEscape(row, col))
          cout << "Free" << endl;

        else
          cout << "Trapped" << endl;
        cout << "Enter row and col of starting position; " << endl<< "negative row stops the processing." << endl;
        cin >> row;
      }
      return 0;
    }

Maze.cpp

    #include "Maze.h"

#include <iostream>
#include <fstream>
#include <string>

Maze::Maze(std::ifstream& inFile)
{
  using namespace std;
  int rowIndex, colIndex;
  inFile >> maxRows >> maxCols;
  string row;
  for (rowIndex = 1; rowIndex <= maxRows; rowIndex++)
  {
    inFile >> row;
    for (colIndex = 1; colIndex <= maxCols; colIndex++)
      maze[rowIndex][colIndex] = row[colIndex-1];
    maze[rowIndex][0] = '+';
    maze[rowIndex][maxCols+1] = '+';
  }
  for (colIndex = 0; colIndex <= maxCols+1; colIndex++)
  {
    maze[0][colIndex] = '+';
    maze[maxRows+1][colIndex] = '+';
  }
}

Maze::Maze (const Maze& anotherMaze)
{
  maxRows = anotherMaze.maxRows;
  maxCols = anotherMaze.maxCols;
  for (int rowIndex = 0; rowIndex <= maxRows+1; rowIndex++)
    for (int colIndex = 0; colIndex <= maxCols+1; colIndex++)
      maze[rowIndex][colIndex] = anotherMaze.maze[rowIndex][colIndex];
}

void Maze::Print()
{
  using namespace std;
  int rowIndex, colIndex;

  cout << "Maze" << endl;
  for (rowIndex = 1; rowIndex <= maxRows; rowIndex++)
  {
    for (colIndex = 1; colIndex <= maxCols; colIndex++)
      cout << " " << maze[rowIndex][colIndex];
    cout << endl;
  }
}

void Try(char[][10], int row, int col, bool& free);

bool Maze::TryToEscape(int startRow, int startCol)
{
  bool free = false;
  Try(maze, startRow, startCol, free);
  return free;
}

void Try(char maze[][10] , int row, int col, bool& free)
{
  if (!free && (maze[row][col]) != '*' && (maze[row][col]) != '+')
    if (maze[row][col] == 'E')
      free = true;
    else
    {
      maze[row][col] = '*';
      Try(maze, row+1, col, free);
      if (!free)
        Try(maze, row-1, col, free);
      if (!free)
        Try(maze, row, col+1, free);
      if (!free)
        Try(maze, row,col-1, free);
    }
}
  • 3
    Look up BFS and DFS, both of which can work in this case to determine whether or not a path exists. BFS also gives you the shortest path. Doing this recursively is probably going to stress your stack space as in the worst case you need to visit every grid square which creates > h * w stack frames in most cases. – Smith_61 Apr 24 '15 at 03:44
  • [Here](http://stackoverflow.com/a/28231125/4505712) is an answer to a related [question](http://stackoverflow.com/q/28228280/4505712). – James Adkison Apr 24 '15 at 03:52
  • Mazes are well handled with the `A*` algorithm. – edA-qa mort-ora-y Apr 24 '15 at 07:45

0 Answers0