Solved
Grid Maze Problem
Posted on 2000-03-09
I've got this problem:
- Given a user specified n by m grid, write a program which computes the number of paths from the bottom left corner to the upper right corner. Paths may only proceed from bottom to top and left to right. For example in the 3 x 3 grid:
g--h--i
| | |
d--e--f
| | |
a--b--c
yields 6 paths
adghi
adefi
abcfi
abefi
adehi
abehi
Output:
The user should be able to specify:
- Output the number of valid paths only
OR
- Output the number of valid paths and all valid paths (i.e. as in the above example)
I've been working on it and here's what I got so far:
VARIABLES
X - Current X co-ordinate
Y - Current Y co-ordinate
XMax - Maximum width of grid
YMax - Maximum height of grid
XModifier - The number of positions "user" moves right
YModifier - The number of positions "user" moves up
PathCount - The number of paths "user" has taken
Begin with:
Xmax = user defined
Ymax = user defined
X = 1
Y = 1
XModifier = 0
Ymodifier = 1
PathCount = 0
Procedure:
1. Increment x,y by respective modifiers until Y reaches max.
2. Increase X until ='s Xmax.
3. Set to x, y to 1, 1 and add 1 to PathCount
4. Increase YModifier by 1.
5. Repeat steps 1 - 4 util YModifier ='s (YMax - 1).
6. Increase XModifier by 1 and set YModifier to 1.
7. Repeat steps 1 - 6 until XModifier ='s (XMax - 1).
The problems I have SO FAR are:
-What about moving something like: right 2, up 3, right 1, up 1, etc?
-What should the proper way of writing the path's be? (ex: (1,1) to (1,5) to (3,5) OR (1,1), (1,2), (1,3), etc)
Any help is apprecated, even if it's just an idea.
Thanks in advance,
Kory