1,105,633 Community Members

Rat Maze help Please DFS, 2d array

Member Avatar
ana_1234
Junior Poster in Training
55 posts since Aug 2010
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

Hello, I am working on an assignment and I am so stuck and I have no clue how to get out. We are giving a maze and we are to find start and finish of the maze. The code is interpreted as giving the "walls" of the cell by looking at the binary representation, with 1's bit = North wall, 2's bit = East wall, 4's bit = South wall, and 8's bit = West wall. (Interpret "up" as North.) For example, code 13 means a cell with North, South, and West walls but no East wall, because 13 = 8 + 4 + 1 = 1101(bin) (no 2's bit). start_row, start_col, goal_row, and goal_col give the starting and ending cell coordinates. Cell coordinates are numbered consecutively from left to right and top to bottom. For example, the left-top corner of the maze is cell (0, 0), and the right-bottom corner is cell (numrows-1, numcols-1).

This is my code so far:

#include <iostream>
#include "Stack.h"
using namespace std;
using namespace cop4530;
struct Position
{
  int x,y;
};

void DFS(Position, Position, int maze[100][100]);
void Success(Stack<Position> S);
void BackTrack(Stack<Position> S);
void Failure(Stack<Position> S);
void Print(Stack<Position> S);

int main()
{
  Position Start, Goal;
  int numrows, numcols, start_row, start_col, goal_row, goal_col;
  int maze [100][100];

  cin >> numrows >> numcols;

  for(int i = 0; i < numrows; i++)
  {
        for(int j = 0; j < numcols; j++)
        {
          cin >> maze[i][j];
        }
  }

  cin >> start_row >> start_col >> goal_row >> goal_col;

  Start.x = start_row;
  Start.y = start_col;
  Goal.x = goal_row;
  Goal.x = goal_col;

void DFS(Position Start, Position Goal, int maze[100][100])
{
  Stack<Position> S;
  int Flag[100][100];


  S.push(Start);
  Flag[Start.x][Start.y] = 1;

  while(!S.empty())
    {
      Position t, n;
      t = S.top();

      if (t == Goal) Success(S);
      if (((maze[Start.x][Start.y] & 0x1) == 0)&&Flag[Start.x][Start.y] == 1)
        S.push(maze[Start.x -1][Start.y]);
      else if (((maze[Start.x][Start.y] & 0x2) == 0)&& Flag[Start.x][Start.y] == 1)
        S.push(maze[Start.x][Start.y + 1]);
      else if (((maze[Start.x][Start.y] & 0x4) == 0)&& Flag[Start.x][Start.y] == 1)
        S.push(maze[Start.x + 1][Start.y]);
      else if (((maze[Start.x][Start.y] & 0x8) == 0)&& Flag[Start.x][Start.y] == 1)
        S.push(maze[Start.x][Start.y - 1]);

      else
        {
         BackTrack(S);
        }
    }
  Failure(S);
}

void BackTrack(Stack<Position> S)
{
  while(!S.empty())
    {
   S.pop();
    }
}

void Success(Stack<Position> S)
{
  while (!S.empty())
    {
      S.pop();
    }
}


void Failure(Stack<Position> S)
{
  while (!S.empty())
    {
      S.pop();
    }
void Print()
{
  //prient element in the stack
  if (S.empty())
    cout << "Stack is Empty" << endl;
  else
    while(!S.empty())
      {
        Position T = S.top();
        cout << "( " << T.x << "," << T.y << " )" << endl;
        S.pop();
      }

}

But I keep getting this error,
maze.cpp: In function âvoid DFS(Position, Position, int (*)[100])â:
maze.cpp:56: error: no match for âoperator==â in ât == Goalâ
maze.cpp:58: error: no matching function for call to âcop4530::Stack<Position>::push(int&)â
Stack.hpp:56: note: candidates are: void cop4530::Stack<T>::push(const T&) [with T = Position]
maze.cpp:60: error: no matching function for call to âcop4530::Stack<Position>::push(int&)â
Stack.hpp:56: note: candidates are: void cop4530::Stack<T>::push(const T&) [with T = Position]
maze.cpp:62: error: no matching function for call to âcop4530::Stack<Position>::push(int&)â
Stack.hpp:56: note: candidates are: void cop4530::Stack<T>::push(const T&) [with T = Position]
maze.cpp:64: error: no matching function for call to âcop4530::Stack<Position>::push(int&)â
Stack.hpp:56: note: candidates are: void cop4530::Stack<T>::push(const T&) [with T = Position]


The first error is because I haven't written that function yet. The rest is because in Stack.hpp the push() function takes in a int but have no clue how to change my original code so that an actual int is being pushed. The professor told me I'm pushing in the wrong thing but I have no clue what I am suppose to be pushing in

Member Avatar
mike_2000_17
21st Century Viking
4,084 posts since Jul 2010
Reputation Points: 2,253 [?]
Q&As Helped to Solve: 800 [?]
Skill Endorsements: 73 [?]
Moderator
Featured
Sponsor
 
0
 

Your stack is a stack of Position objects. You need to push Position objects onto it, not integers. For example, at line 55, you could do this:

S.push(Position(Start.x -1,Start.y));
Member Avatar
ana_1234
Junior Poster in Training
55 posts since Aug 2010
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

void push(const T& val): push a new element val into the stack.

I tried the S.push(Position(Start.x -1, Start.y) and even more errors displayed.

So I need to push the value of the new element assuming the type T. I tried this but sill not working.

if (((maze[Start.x][Start.y] & 0x1) == 0)&&Flag[Start.x][Start.y] == 1)
        S.push(S);
      else if (((maze[Start.x][Start.y] & 0x2) == 0)&& Flag[Start.x][Start.y] == 1)
        S.push(S);
      else if (((maze[Start.x][Start.y] & 0x4) == 0)&& Flag[Start.x][Start.y] == 1)
        S.push(S);
      else if (((maze[Start.x][Start.y] & 0x8) == 0)&& Flag[Start.x][Start.y] == 1)
        S.push(S);

now I'm getting this error
maze.cpp:59: error: no matching function for call to âcop4530::Stack<Position>::push(cop4530::Stack<Position>&)â
Stack.hpp:56: note: candidates are: void cop4530::Stack<T>::push(const T&) [with T = Position]
maze.cpp:61: error: no matching function for call to âcop4530::Stack<Position>::push(cop4530::Stack<Position>&)â
Stack.hpp:56: note: candidates are: void cop4530::Stack<T>::push(const T&) [with T = Position]
maze.cpp:63: error: no matching function for call to âcop4530::Stack<Position>::push(cop4530::Stack<Position>&)â
Stack.hpp:56: note: candidates are: void cop4530::Stack<T>::push(const T&) [with T = Position]
maze.cpp:65: error: no matching function for call to âcop4530::Stack<Position>::push(cop4530::Stack<Position>&)â
Stack.hpp:56: note: candidates are: void cop4530::Stack<T>::push(const T&) [with T = Position]

Member Avatar
mike_2000_17
21st Century Viking
4,084 posts since Jul 2010
Reputation Points: 2,253 [?]
Q&As Helped to Solve: 800 [?]
Skill Endorsements: 73 [?]
Moderator
Featured
Sponsor
 
0
 

The type T is equal to the type Position (T is a placeholder for the type that you put between <> when declaring the stack). It says so in the error message: "[with T = Position]".

You need to push a variable of type Position, there is absolutely no doubts about that, don't try anything else, it won't work.

The reason you are getting errors with the code I suggested is because you don't have a constructor for Position (I'm sorry I didn't point that out early, it's just that the coming standard won't require it and I got used to that). So, you need to add a few things to your Position struct:

struct Position
{
  int x,y;
  Position(int aX,int aY) : x(aX), y(aY) { }; //constructor.
  bool operator ==(const Position& rhs) const { return ((x == rhs.x) && (y == rhs.y)); };
};
Member Avatar
ana_1234
Junior Poster in Training
55 posts since Aug 2010
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

Thank you for your help but I am getting the same error code

maze.cpp: In function âint main()â:
maze.cpp:21: error: no matching function for call to âPosition::Position()â
maze.cpp:9: note: candidates are: Position::Position(int, int)
maze.cpp:7: note: Position::Position(const Position&)
maze.cpp:21: error: no matching function for call to âPosition::Position()â
maze.cpp:9: note: candidates are: Position::Position(int, int)
maze.cpp:7: note: Position::Position(const Position&)
maze.cpp: In function âvoid DFS(Position, Position, int (*)[100])â:
maze.cpp:56: error: no matching function for call to âPosition::Position()â
maze.cpp:9: note: candidates are: Position::Position(int, int)
maze.cpp:7: note: Position::Position(const Position&)


if I comment out Position(int aX,int aY) : x(aX), y(aY) { }; //constructor, I get a the same problem in lines
maze.cpp: In function âvoid DFS(Position, Position, int (*)[100])â:
maze.cpp:61: error: no matching function for call to âPosition::Position(int&, int&)â
maze.cpp:7: note: candidates are: Position::Position()
maze.cpp:7: note: Position::Position(const Position&)
maze.cpp:63: error: no matching function for call to âPosition::Position(int&, int&)â
maze.cpp:7: note: candidates are: Position::Position()
maze.cpp:7: note: Position::Position(const Position&)
maze.cpp:65: error: no matching function for call to âPosition::Position(int&, int&)â
maze.cpp:7: note: candidates are: Position::Position()
maze.cpp:7: note: Position::Position(const Position&)
maze.cpp:67: error: no matching function for call to âPosition::Position(int&, int&)â
maze.cpp:7: note: candidates are: Position::Position()
maze.cpp:7: note: Position::Position(const Position&)

You
This article has been dead for over three months: Start a new discussion instead
Post:
Start New Discussion
View similar articles that have also been tagged: