Velocity Reviews > C++ > Tips anyone

# Tips anyone

pleatofthepants
Guest
Posts: n/a

 02-29-2008
Ok, I have to solve the "Rat Maze" problem"

I am opening a file called maze.txt which looks similar to this

20 *this is # of rows
20 *this is # of columns
9 *starting row
9 *starting column
11111111111111101111
10101010101010101011
10000010001000101001
10111000100010000011
10111111111111111011
etc....

I have to find the path out of the maze using recursion

This is what I have come up with for the recursion function, ant tips?

int maze(int data[][])
{
data[r][c];

if( data[r][0] | data[0][c] | data[r][19] | data[19][c] == 0) //
base case
{
cout << "The Rat Is Free!" << endl;
}
if( data[r+1][c] == 0 )
{
cout << "Move Up" << endl;
return maze(data[r+1][c]);
}

if ( data[r-1][c] == 0 )
{
cout << "Move Down" << endl;
return maze(data[r-1][c]);
}

if ( data[r][c+1] == 0 )
{
cout << "Move Right" << endl;
return maze(data[r][c+1]);
}

if ( data[r][c-1] == 0 )
{
cout << "Move Left" << endl;
return maze(data[r][c-1]);
}

else
{
cout << "Rat your are stuck" << endl;
}
}

Klarth
Guest
Posts: n/a

 02-29-2008
On Feb 29, 2:17 pm, pleatofthepants <(E-Mail Removed)> wrote:
> Ok, I have to solve the "Rat Maze" problem"
>
> I am opening a file called maze.txt which looks similar to this
>
> 20 *this is # of rows
> 20 *this is # of columns
> 9 *starting row
> 9 *starting column
> 11111111111111101111
> 10101010101010101011
> 10000010001000101001
> 10111000100010000011
> 10111111111111111011
> etc....
>
> I have to find the path out of the maze using recursion
>
> This is what I have come up with for the recursion function, ant tips?
>
> int maze(int data[][])
> {
> data[r][c];
>
> if( data[r][0] | data[0][c] | data[r][19] | data[19][c] == 0) //
> base case
> {
> cout << "The Rat Is Free!" << endl;
> }
> if( data[r+1][c] == 0 )
> {
> cout << "Move Up" << endl;
> return maze(data[r+1][c]);
> }
>
> if ( data[r-1][c] == 0 )
> {
> cout << "Move Down" << endl;
> return maze(data[r-1][c]);
> }
>
> if ( data[r][c+1] == 0 )
> {
> cout << "Move Right" << endl;
> return maze(data[r][c+1]);
> }
>
> if ( data[r][c-1] == 0 )
> {
> cout << "Move Left" << endl;
> return maze(data[r][c-1]);
> }
>
> else
> {
> cout << "Rat your are stuck" << endl;
> }
>
> }

The way it is currently written, it looks like you get some confusing
output! For example, I can see that it is possible for your program's
output to be:

The Rat Is Free!

Or even a combination of "The Rat Is Free" and one of the other
movement messages (and make further unnecessary moves). Also, if your
rat finds a dead end, how does your algorithm prevent going backwards
and towards the start? I don't see how you keep track of which
direction the rat came from, so it looks like your algorithm will
retry going in the direction that you came from.

On a large maze, it also looks like there is going to a heck of a lot
of recursive calls. Perhaps you can move forward using a while loop
and use recursive call to change or try different directions?

Jim Langston
Guest
Posts: n/a

 02-29-2008
pleatofthepants wrote:
> Ok, I have to solve the "Rat Maze" problem"
>
> I am opening a file called maze.txt which looks similar to this
>
> 20 *this is # of rows
> 20 *this is # of columns
> 9 *starting row
> 9 *starting column
> 11111111111111101111
> 10101010101010101011
> 10000010001000101001
> 10111000100010000011
> 10111111111111111011
> etc....
>
> I have to find the path out of the maze using recursion
>
> This is what I have come up with for the recursion function, ant tips?
>
> int maze(int data[][])
> {
> data[r][c];
>
> if( data[r][0] | data[0][c] | data[r][19] | data[19][c] == 0) //
> base case
> {
> cout << "The Rat Is Free!" << endl;
> }
> if( data[r+1][c] == 0 )
> {
> cout << "Move Up" << endl;
> return maze(data[r+1][c]);
> }
>
> if ( data[r-1][c] == 0 )
> {
> cout << "Move Down" << endl;
> return maze(data[r-1][c]);
> }
>
> if ( data[r][c+1] == 0 )
> {
> cout << "Move Right" << endl;
> return maze(data[r][c+1]);
> }
>
> if ( data[r][c-1] == 0 )
> {
> cout << "Move Left" << endl;
> return maze(data[r][c-1]);
> }
>
> else
> {
> cout << "Rat your are stuck" << endl;
> }
> }

There is an algorithm for pathfinding that would work perfect for this, but
I'm fairly sure this is homework and the professor wants you to come up with

Think of it this way though as a general idea.

Look at your current position and see if it is free.
If not call this function with one position north.
If not call this function with one positon south.
If not call this function with one postion east.
If not call this function with one positon south.

That is a very base and doesn't take into account a lot of things which you
need to code for. The function will need to be called wtih the postion to
check, and also need to return something indicating what it found there.
Impassible, opne or free.

Also, it won't find the most effecient way out, just a way out.

Another possibiltiy is the right wall way. You follow a right wall (or left)
until you are out. This works in all mazes such as this unless the walls
are not continiguous.

I don't want to give too much because this is info, but the function you
have shown is not recursive at all. A recursive function calls itself.

--
Jim Langston
http://www.velocityreviews.com/forums/(E-Mail Removed)

Triple-DES
Guest
Posts: n/a

 02-29-2008
On 29 Feb, 11:19, "Jim Langston" <(E-Mail Removed)> wrote:
> I don't want to give too much because this is info, but the function you
> have shown is not recursive at all. *A recursive function calls itself.

His function is recursive, look at the points of exit.

DP

James Kanze
Guest
Posts: n/a

 02-29-2008
On Feb 29, 12:33 pm, Triple-DES <(E-Mail Removed)> wrote:
> On 29 Feb, 11:19, "Jim Langston" <(E-Mail Removed)> wrote:

> > I don't want to give too much because this is info, but the
> > function you have shown is not recursive at all. A
> > recursive function calls itself.

> His function is recursive, look at the points of exit.

Yes. The problem is that recursion isn't enough; he needs
backtracking. Basically, at each level of recursion, try up,
right, down and left until one works. The recursive function
must return a value to indicate whether it succeeded or not.
Basically, a loop along the lines of:

bool
try( position )
{
bool found = false ;
for ( direction in up, right, down, left and ! found ) {
if ( open( position + direction ) &&
! visited( position + direction ) ) {
found = try( position + direction ) ;
}
}
return found ;
}

(Obviously, this needs a good deal of fleshing out. That for
isn't going to pass as written, and you also need checks to end
the recursion, and possibly to avoid wandering off the edges of
the maze---although that could also be handled in open(). But
the basic idea is there. And I sort of like the idea of
declaring direction as an enum, with position a class type which
small program which will generate an iterator over an enum, so
the for loop becomes very simple.)

--
James Kanze (GABI Software) email:(E-Mail Removed)
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

red floyd
Guest
Posts: n/a

 02-29-2008
pleatofthepants wrote:
> Ok, I have to solve the "Rat Maze" problem"
>
> I am opening a file called maze.txt which looks similar to this
>
> 20 *this is # of rows
> 20 *this is # of columns
> 9 *starting row
> 9 *starting column
> 11111111111111101111
> 10101010101010101011
> 10000010001000101001
> 10111000100010000011
> 10111111111111111011
> etc....
>
> I have to find the path out of the maze using recursion
>
> This is what I have come up with for the recursion function, ant tips?
>
> int maze(int data[][])

This line should not compile.
> {
> data[r][c];

>
> if( data[r][0] | data[0][c] | data[r][19] | data[19][c] == 0) //
> base case
> {
> cout << "The Rat Is Free!" << endl;
> }
> if( data[r+1][c] == 0 )
> {
> cout << "Move Up" << endl;
> return maze(data[r+1][c]);
> }
>
> if ( data[r-1][c] == 0 )
> {
> cout << "Move Down" << endl;
> return maze(data[r-1][c]);
> }
>
> if ( data[r][c+1] == 0 )
> {
> cout << "Move Right" << endl;
> return maze(data[r][c+1]);
> }
>
> if ( data[r][c-1] == 0 )
> {
> cout << "Move Left" << endl;
> return maze(data[r][c-1]);
> }
>
> else
> {
> cout << "Rat your are stuck" << endl;
> }
> }

Jim Langston
Guest
Posts: n/a

 03-01-2008
Triple-DES wrote:
> On 29 Feb, 11:19, "Jim Langston" <(E-Mail Removed)> wrote:
>> I don't want to give too much because this is info, but the function
>> you have shown is not recursive at all. A recursive function calls
>> itself.

>
> His function is recursive, look at the points of exit.

yes, you are right. I missed that. It's just not effective.

--
Jim Langston
(E-Mail Removed)

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post jayeshsorathia@gmail.com ASP .Net 1 07-31-2012 01:03 AM diesel Computer Support 0 05-31-2006 01:00 PM Cornelius Fichtner Firefox 0 12-18-2003 11:50 PM