programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# moving through 2D arrays

Deyna Cegielski
Ranch Hand
Posts: 60
i have a 2d array (a maze) which is filled with true and false (true = free space, false = wall).

using a stack im trying to write a method to find the correct path through the maze by first going right (if i can), then down(if i can), then left...and then up.

each free point i goto gets set as visited and if i come to a dead end (cant go right down left or up) this point is set as "discard" and i move back a step (using the stack) and check to see if going right down left or up is a free space, not doing anything if it is a wall or it has been discarded. i can do this with recursion but without im having difficulties, i can visualise what to do its writing the code im having troubles with.

Norm Miller
Ranch Hand
Posts: 56
This is a problem which really solves best with a recursive solution. If you already have that, why change it? If you must change it, you can make a recursive solution into an iterative one. I googled for a couple minutes using the keywords "recursion" and "iteration" and found several sites showing how it is done.

Ernest Friedman-Hill
author and iconoclast
Sheriff
Posts: 24217
38
Originally posted by Deyna Cegielski:
i can visualise what to do its writing the code im having troubles with.

OK, describe what you want to do, and we'll give you some pointers.

Deyna Cegielski
Ranch Hand
Posts: 60
sorry...

"im trying to write a method that moves through a 2d array point by point. at each point it trys to go right if it can it goes right if it cant it trys to go down, then left, then up. if it can move then it will at the process is repeated for the new point. this can be done with recursion but i have no idea how to implement this as an iterative proceess and im not allowed to use recursion. please help!"

Deyna Cegielski
Ranch Hand
Posts: 60
maybe its easier if i translate that into a bit of pseudocode...

1.for each point
is point up "free space", if so go there, repeat 1.
is point to right "free space", if so go there, repeat 1.
is point down "free space", if so go there, repeat 1.
is point to left "free space, if so go there, repeat 1.

the implementation at each step i can do myself, its setting up the above as an interative process i cant do. any help would be be greatly appreciated.

Layne Lund
Ranch Hand
Posts: 3061
Also, you might need a stack to help back up when you reach a dead end.

Layne

Stan James
(instanceof Sidekick)
Ranch Hand
Posts: 8791
A little more detail on the idea above ... Recursion gives you a new set of local variables on the JVM's stack. To convert from recursion to iteration you can put your local variables on your own stack instead. If you're in JDK 5 you have a Stack class, otherwise you can use a LinkedList like a stack.

I'd make a little data-only object with all the local variables I need, maybe row, column, length of path, etc. Then any time you were thinking about calling yourself recursively, push the current object onto the stack and initialize a new one. Where the recursion returned, pop the prior object off the stack again.

I remember doing this in COBOL to evaluate an expression with nested parens. (Still have the code on this PC!) Ah, the good old days!

Layne Lund
Ranch Hand
Posts: 3061
Originally posted by Stan James:
If you're in JDK 5 you have a Stack class, otherwise you can use a LinkedList like a stack.

The Java API has had a Stack class since JDK 1.0, according to the javadocs.
Layne
[ November 30, 2004: Message edited by: Layne Lund ]