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