Jochus wrote:
"Gernot Frisch" schreef:
Do _not_ do such algorithms recursively - it's gonna go stack overflow
in the last test before shipping the release version, believe me.
Yes, I know ... But that is the thing we are learning. For large fields,
it's gonna go stack overflow. I'll ask my tutor to use YOUR solution, but
I'm afraid he will disagree and say I have to use his solution ...
So what *is* his solution.
The recursion is quite easy to do. Let us forget for the *shortest*
path for the moment. Just concenrate on *a* path.
BTW: The whole concept is called backtracking. I usually gave my
students a variation of your assignment, called: "How the mouse gets
the cheese": There is a labyrinth in a 2D array. Each array element
is marked as beeing either:
* empty space (' ')
* a wall ('*')
* the mouse ('M')
* the cheese ('C')
The goal is to find (using backtracking) a path from the mouse to
the chesse. As said: If you know backtrakcking this is quite simple
to do. Once that part runs, it is easy to generalize it such that the
shortest path can be found.
I will use that assignment in the discussion, since I don't want to do
your homework.
As most of the time with recursion you first have to think of a few
things. First you need to a global understanding of what your function
has to do:
Given a coordinate in the array (2 indices), find a way from that position
to the goal.
Plain and simple.
Next you should think about the trivial case. That is: When is this problem
so easy, that a solution can be given immediatly?
In the above example, the answer is (don't laugh it really is that trivial),
"When the coordinates already hold the cheese." In this case you found a
solution.
Are there any other trivial cases?
Yes, sure. When there is a wall at the position in question. Obviously the cheese
cannot be at this position. In this case case the search failed (for that position).
And in the other - non trivial - cases: Well, just try if the position to the north
leads to the chesse. If it does, fine you found a solution. The position in question
is part of that solution. If it does not, try to the south. If solution ....
If not, try west .... If not try east.
And that's it, for just one small detail: The mouse needs to keep track of what
positions it already tried, such that it will never try the same position again.
How is that done: Simple: just mark the array element with some character, lets
say a '.'. So we have one more trivial case: When the searched position contains
a '.' the search failed for that position, because the mouse had visited that
position already.
So your function will be
bool Search( int IndX, int IndY )
That is: search the maze at position IndX/IndY for the cheese.
The return value will either be true or false, depending if the
cheese was found or not.
Now filling in what we already know from the above:
bool Search( int IndX, int IndY )
{
// Trivial case 1:
// if that position contains the cheese: hurra
if( Maze[IndY][IndX] == 'C' ) {
cout << "Hurra: Found the cheese at " << IndX << " " << IndY << "\n";
return true;
}
// Trivial case 2:
// if that position contains a wall: sniff, the cheese cannot be here
if( Maze[IndY][IndX] == '*' )
return false;
// Trivial case 3:
// Position already visited: There is no sense in testing again. Cheese not found
if( Maze[IndY][IndX] == '.' )
return false;
// The mouse entered empty space, try north south, east, west
// If one of those searches leads to the chesse: fine
//
// But first mark that the mouse entered this field already:
Maze[IndY][IndX] = '.';
if( Search( IndX, IndY + 1 ) ||
Search( IndX, IndY - 1 ) ||
Search( IndX - 1, IndY ) ||
Search( IndX + 1, IndY ) ) {
cout << "Path " << IndX << " " << IndY << endl;
return true;
}
// sniff: The cheese is not at position IndX/IndY and a search
// to the north/south/east/west didn't come up with the cheese
// report failure to caller
return false;
}
and that's it.
A quick test program reveals:
#include <iostream>
using namespace std;
char Maze[7][16] = { "***************",
"* C * *",
"****** * *** **",
"* * * **",
"* ****** * ** *",
"* * * *",
"***************" };
bool Search( int IndX, int IndY )
{
.... See above
}
int main()
{
if( Search( 11, 3 ) )
cout << "Cheese found" << endl;
else
cout << "Cheese not found" << endl;
}
Step it through with your debugger until you clearly
understand how everything works. It might also be a
good idea to insert additional output statements
into Search: eg.
bool Search( int IndX, int IndY )
{
cout << "Testing position " << IndX << " " << IndY << "\n";
// Trivial case 1:
// if that position contains the cheese: hurra
if( Maze[IndY][IndX] == 'C' ) {
cout << "Hurra: Found the cheese at " << IndX << " " << IndY << "\n";
return true;
}
// Trivial case 2:
// if that position contains a wall: sniff, the cheese cannot be here
if( Maze[IndY][IndX] == '*' ) {
cout << "Hit a wall!\n";
return false;
}
....
Another hint: In your first attempts to follow the program flow in your
debugger, make sure the mouse starts near the cheese! Eg. a position
4 1 would be a good candiate.
Once you understand, how the mouse gets to the cheese, apply what you
have learned to your real problem. But: First make your program search
any path, then concentrate on letting it search for the shortest path!
--
Karl Heinz Buchegger
kb******@gascad.at 
