[Assignment Help] Need help implementing a recursive depth first maze runner

Hi, say I need to write a recursive depth-first maze running algorithm that takes the following signature:

 
  int runMaze(Maze& theMaze, int path[], int fromCell, int toCell);


The function should return the number of valid paths taken, and the path array should contain all of these valid paths in order.

How do I go about indexing the path array to add or remove elements in recursive calls?

I'm limited to plain c arrays (no STL), and I can't change the function signature.

I'm just really confused on how to keep track of the indices in the path array, but otherwise, I think I have the general backtracking algorithm down.

Since the array decays into a pointer, and there is no size passed into the array, how do I add elements to it? In addition, when I need to backtrack, how would I go about removing the last element? What is my index?

If anyone can point me into the right direction I would deeply appreciate it.
Last edited on
need to see the maze and partial output expected, do you have a sample test case to run?

you can't add locations to an array, all you can do is index up to what it holds.
you can find its size, if you need that.
the size of an array: sizeof(arr)/sizeof(arr[0]);

index can be static, but I don't know if that answers your question.

1
2
3
4
5
6
7
8
9
10
void foo()
{
   static int index = 0;
    foo(next);
     if(making progress)
      index++;
  else  if(backtrack)
      index--;
}

here index is the same variable across ALL the recursive calls.

to remove the last element if you got stuck, you just change the index backwards and the next valid entry will overwrite that. you can explicitly zero out that cell or whatever sentinel value you want to use to indicate 'invalid' so that if it finds the exit any subsequent data is marked invalid for you.

depending on what is in path, you can also brute force the thing. if path is an array of say 1000 ints, all of them initialized to say -42 which you have defined to mean 'invalid, unused cell' then you can do it via iteration too, fire off index at zero and iterate until the cell at the current index == -42 and you have found the next spot to write into, and can go backwards (if not at the initial location!) if there is nowhere to go from a step... the static idea eliminates the hunt and peck extra looping, is all.
Last edited on
Hey, thanks for the response. I considered the static index approach a while ago and it did work, however, it only worked for a single test. For subsequent tests in the driver program, the static index would need to be reset some how, which I don't think is possible?

Also, the sizeof(arr)/sizeof(arr[0]) won't work because the array passed into the function will decay into a pointer. So the sizeof evaluation won't produce the expected results.

Either way, do you think that the specifications for this assignment are not feasible? The more I try to work this out, the more I start to think that the requirements just aren't realistic (and quite silly to be quite honest).
Last edited on
yea you need a reset if you need to re-run the code.

I dunno what is possible with your inputs, maybe 'if fromcell is something then index = 0' or base it off both from and to cells, is that possible?

if you can't detect it from the inputs, you have to do an ugly or find another way.
the ugly way is to arrange the recursion so the final return statement at the end of it all, the very last one, when that returns back to the original calling functon set index back to zero. It may take some hand waving to make that happen. The issue is that the static variable retained its last value -- it exists for the life of the entire program and keeps its last value... that is what the static did to it.

the requirements are silly. this happens in real life too, sometimes :) Professors LOVE to give assignments where they tell you to do crap without any tools allowed to be used. Its nonsense, but ... well, an old song says "I spent 4 years prostrate to the higher mind, got my papers and I was free"
Last edited on
Ah, I just saw the edit you made to one of your previous comments: "you can also brute force the thing. if path is an array of say 1000 ints, all of them initialized to say -42 which you have defined to mean 'invalid, unused cell..."

I had also considered this previously as well. The thing is, the path array does not initialize any of the values, they are all garbage values when passed in :(
Last edited on
ok, well one more idea...
you can always use the 0th location of path, then.
call it with
runmaze(themaze, &path[1], blah, blah) //make it so path[0] is the current location to write into each recursive call. I am not 100% sure if it works with [] parameter vs * parameter right this second. I never use [] and forget the subtle differences.

if that does not work, you can do one final thing:
make a new function that does ALL the work with more parameters (so you can pass index in).
have their function just call yours, so it keeps their format, but yours does all the recursion and work.

there is probably some other clever way to do it, but I am having trouble getting into one hand behind my back mode tonight.
Last edited on
Since path is a pointer all you need to do is pass path + 1 to indicate the next position.
Ugh, I haven't touched C++ in too long and have been working with too much higher level languages like javascript and C# that I forgot I can just use pointer arithmetic. That eliminated the need for indexing entirely... Thanks for pointing it out, dutch. Got everything working now.
Topic archived. No new replies allowed.