We help IT Professionals succeed at work.

# Grid Maze Problem

on
540 Views
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

abcfi
abefi
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.

Kory
Comment
Watch Question

## View Solution Only

CERTIFIED EXPERT
Most Valuable Expert 2014
Top Expert 2015

Commented:
Think of Pascal's Triangle
Quid, Me Anxius Sum?  Illegitimi non carborundum.
CERTIFIED EXPERT

Commented:
For each step you are about to take there are two choices, up or to the right.

These choices sometimes may not exist eg you are at the top or at the right of the array.

So you have a recursive problem if you know what recursion is.  This is the easiest way to solve it.

You will need an array to store the path you are travelling and this will be passed recursively.  You will also need to pass another variable recursively and this is the number of paths found.

What sort of array could this be?  How about an array of char that is initialised to E for empty.  At each step the array point you are at is changed to either U or R for Up or to the Right.  In this way you are saving the path you are travelling.

This may explain ozo's hint.

Commented:
well... another way of thinking of it is just place R ups in a path of length R+C (R x C grid) so... (R+C) choose R

Commented:
oops (R+1) x (C+1) grid

Commented:
is there a maximum values for M and N ?

Commented:
i think the most acceptable solution is to build a binary tree where nodes
are points with x and y coordinates - for each node make two other nodes (one-up and one-right), and keep growing the tree in such way until every tree branch comes to the upper-right corner; in that way when you will have
a complete tree, then the number of the branches would be number of paths or something like that

Commented:
if you REALLY want a program, i think i could write it, but i'm quite busy for that time, so please do it yourself using the simple algorithm i gave to you..

Commented:
Jack,
Before I give ya the points, I'm going to have to "research" your idea. (I haven't used Binary Trees before) One question I have about your answer. Sure I can count the number of branches to find out the number of paths, but is it able to tell me what the paths are too?

Alisher,
No, there is no max value for M and N. They are both user defined.

_lychee_,
Could you please explain your idea again? I don't think I caught on.

dbrunton,
Do you mean entering a value (right or up) in the array for each and every point in the grid? That could be one enormous array if the grid is large.

ozo,
Pascal's triangle?

Thanks all for the ideas. I'm looking into all of them. If anyone has anymore ideas, go right ahead and post them!

TKS,
Kory
Quid, Me Anxius Sum?  Illegitimi non carborundum.
CERTIFIED EXPERT

Commented:
An array of char.  If you have a 12 by 12 array this is a 144 bytes.  If you have unusual arrays like 200 by 200 it will get very large, in this case an array of 40,000 bytes.

Commented:
Jack_p50,
I looked at Binary trees briefly last night. Still a few questions. How would I put in the (X,Y) co-ordinate in each node? In each example I have seen, it is only possible to put strings and/or integers into the nodes.
Commented:
This one is on us!
(Get your first solution completely free - no credit card required)

Commented:
>How would I put in the (X,Y) co-
>ordinate in each node? In each example
>I have seen, it is only possible to
>put strings and/or integers into the
>nodes.

If you WERE to use a binary tree structure, you can store ANY type of data in a node.  If you wanted to store both the X and Y coordinate, you could declare a structure

type
TPoint = record
x, y :integer;
end;

and then use TPoint as the data type for each of your nodes (as opposed to strings, integers, etc.)

Commented:
by the way, if you rules do not allow diagonal movement (which I apparently overlooked), you can replace the for x1 = ... block with the following code:

if (x+1) <= width then
traverse(x+1,y1);
if (y+1) <= height then
traverse(x,y+1);

Commented:
if u have R rows and C columns, then to get to the top right using only up and right, u obviously need
R-1 ups and C-1 rights

so in ur path that is length (R+C-2), u need C-1 rights or R-1 ups (it's the same)

so, total number of ways = (R+C-2) choose (C-1) [like nCr]

can get the path by moving the ups and rights around: like for a 3x3:
UURR -> URUR -> URRU -> RUUR -> RURU -> RRUU
basically start with all on one side (in this case U is on the left), then start moving the last U to the right, until u hit the edge, then advance the next U and reset the U...
argh the explanation's not good but it's just how u would systematically get all the combinations....

for 3Us and 2Rs, it would be like:
UUURR -> UURUR -> UURRU -> URUUR -> URURU -> URRUU -> RUUUR -> RUURU -> RURUU -> RRUUU

see the pattern?

btw, what ozo means by pascal's triangle is like if u take the top right corner to be the top of a triangle and the up to right diagonal to be the base, and u put the number of ways to get to the topright on each grid intersection, u'll see that it is a pascal triangle

Commented:
yes of course it would say you the paths
let's see :

g h i
d e f
a b c

we create a tree starting at (a) point and then going up/right from every
item (if there's way up/right). check this tree out :

start                   ___________(a)__________
/                                               \
___(b)____                              ___(d)____
/                  \                            /                    \
__(e)__        __(c)__                __(e)__          __(g)__
/            \     /             \             /             \       /             \
(f)         (h)   (f)           nil         (h)           (f)   (h)            nil
/ \         / \    |  \                       / \             |    / \
(i) nil    nil (i) nil (i)                   (i) nil           |  (i)  nil
/ \
nil (i)

from that tree you must see (if you're not blind, and i think you're not)
that there're only 6 paths ending at the final (i) point, and you obviously
see the paths themselves

now got it?

Commented:
by the way, call me Jack

there are several solutions :

1) write the tree yourself with two coordinates
2) string "4 3"  stands for x=4, y=3
3) use longints instead of integers (if you want big x,y) and store
x in the lower word and y in the higher (or vice versa, as you wish)

in any case, any of these solutions are quite useful

i'd recommend you 1), but if you're in hurry, the better would be 3)

ask any questions if you got them

Commented:
I would do a simpler soloution
(sorry jeck.... :-))

lets take the exmple.
it is clear that the path consist
of two steps up and two steps right.
lets say that 0 - represents up
1 - represent right.

for 3*3 grid there are 4 steps paths.

g--h--i
|  |  |
d--e--f
|  |  |
a--b--c

yields 6 paths

a 0 d 0 g 1 h 1 i
a 0 d 1 e 1 f 0 i
a 1 b 1 c 0 f 0 i
a 1 b 0 e 1 f 0 i
a 0 d 1 e 0 h 1 i
a 1 b 0 e 0 h 1 i

we got a four digits binary number
with the rule that the number
of one's is Equal to the number of zero's. (and it makes sence !)

(just omit all other numbers...)

so:

D = num of digits M+N-2
range of numbers 2^(D-1) - 2^D-1

to find digit is very simple
(divide with 2 until you get 0, and the reminder is the digit...)

AND no need need with more the a simple
loop inside a loop !!!

Yair

Commented:
I was not able to "ANSWER" this question. But I think my solution is on right and simplest track. Hope you like this.

As in your example there are m X n(3 X 3) lines.
BY any means if you use (m-1) ups and (n-1) rights then you
are at the destination.
Hence the problem reduces to just  an array manupulation
with fixed number of U(ups) and fixed number of R(rights)
All possible combinations of U and R is the answer.

thus in your example m=2 and n=2
hence UURR URUR URRU RRUU RURU RUUR
are the combinations.

I will need some more time to code it.

Commented:
sigh... datz my soln actually (read up)...

anyway, a way of doing it is:

1) generate a starting string consisting of all U's and R's separated:
eg. UUURR

2) starting from the right of the string, look for the first R, (let the number of U's skipped be N), and the first U to the left of the R (this U is called "the U")

3) advance "the U" one space to the right, and put the N U's that u skipped to "the U"'s immediate right...

4) this is a solution

5) repeat from (2) until there are no more U's on the left of the first R (ie. RRUUU)...

Commented:
so, first u get
UUURR

then, N = 0, u advance "the U" (which is the 3rd character)

UURUR

then, N=0 still, u advance "the U" (4th character)

UURRU

then, N=1, u advance "the U" (2nd character) and put the 1 Us to its immediate right:

URUUR

and so on... it's the same sequence as the one i proposed earlier (i think)

Commented:
i think this'll work (haven't tested it tho...):

suppose the string S is the start string... with Us to the left and Rs to the right; i, j, k all integers

while true do begin
{S contains a solution here}

i := Length(S);
j := 0;
while (S[i] <> 'R') do begin
S[i]:='R';
dec(i);
inc(j);
end;
while ((i > 0) and (S[i] <> 'U')) do dec(i);
if (i = 0) then break;
S[i] := 'R';
for k := i+1 to i+1+j do S[k] := 'U';
end;

Commented:
hey sucker, don't call me jeck

Commented:
i suppose that tree is maybe not most fast but most clear and obvious solution

Commented:
Ofcourse, the number of one's should be
equal to M-1 and the number of zero's is N-1...
I think running on integers is
much easier then strings.

> hey sucker, don't call me jeck
we don't use this kind of language here,
but there are other forums on the web that you may.
I am sorry, its a typo.

Yair

Commented:
running on integers is much easier??

how're u gonna generate ur numbers? by running thru all 2^(m+n-2) numbers?

what if (m+n-2) is too large?

if u're talking about an integer array, i don't think there's a great deal of time savings from a string...

Commented:
yairy,
In your example, it is not possible to create the array of the points travelled (ie: (1,1),(2,1), etc) unless you create another loop incrementing X or Y respectivly.

_lychee_ & sumant,
In your example it appears to be the same problem that I have with yairy's answer.

Commented:
I disagree with you.

instead of printing the binaric number,
scan its digits.
keep coord. indexes of the matrix corner.
print the value they point to and increase the proper
(x/y) index value according to the digit.

Yair

Commented:
can you explain why did you reject my answer ?

Commented:
>running on integers is much easier??
Yes,
a simple FOR command.

>how're u gonna generate ur numbers? by running thru all 2^(m+n-2) numbers?
Yes,
you can solve it in a iterative mode or recursive mode
but anyway this the Range of solutions.
any solution work as hard.

>what if (m+n-2) is too large?
>if u're talking about an integer array, i don't think there's a great deal of time savings from a string...

Well, the number of solutions in order of 2^(m+n-2).
When this value (m-n-2) equals 30
you have 2^30 = 1,000,000,000 possible solutions.
so I guess running on large scale matrixes
(over 32 ==> number of bits in a WORD)
is not too pratical in terms of TIME (~4*10^9).

one can use 64 bits word (most OS's supports that)
and really can be sure.

another way is to two, four intergers....

Yair

Commented:
This is the simplest implimentation of my alg. This program works just fine and gives correct output.

program grid;
uses crt;

const C = 20;
var a : array[1..C] of char;
i,row,col,m,n,Rs,Us,count : integer;

begin
clrscr;
write('Enter Horizontal lines: ');
write('Enter Vertical lines: ');
if (row < 2) or (col < 2) then
begin
write('Invalid input.');
halt;
end;
count:=1;
for i:=1 to (row-1) do a[i]:='U';

for i:=i+1 to (row-1) + (col-1) do a[i]:='R';

writeln(count:3,' st Combination: ',a);
while true do
begin
m:=(row-1)+(col-1);
Us:=row-1;
Rs:=col-1;
while true do
begin
if a[m]='R' then
begin
m:=m-1;
if m=0 then break;
Rs:=Rs-1;
end
else if Rs < (col-1) then
begin
a[m]:='R';
Rs:=Rs+1;
m:=m+1;
Us:=Us-1;
break;
end
else
begin
m:=m-1;
Us:=Us-1;
end;
end;
if m=0 then break;

while (Rs < (col-1)) or (Us < (row-1)) do
begin
if Us < (row-1) then
begin
a[m]:='U';
Us:=Us+1;
m:=m+1;
end
else
begin
a[m]:='R';
m:=m+1;
Rs:=Rs+1;
end;
end;
count:=count+1;
writeln(count:3,' th Combination: ',a)
end;
write('Press any key to continue...');
end.

Commented:
Binary tree is really an expensive way (in memory point of view) I think.

Commented:
I don't think giving her/him the full solution is to the point. It shouldn't be our task.

Commented:
kory:
given the turnings made it is definitely possible (and trivial) to get the coordinates out... i'm sure u can code it...

yairy:
the number of solutions is definitely NOT on the order of 2^(m+n-2).... it is on the order of (m+n-2)C(n-1)... potentially MUCH less than 2^(m+n-2)... take M=1000000 and N=1 for eg... ur algo will take ages 2^999999 but there's only 1 path...

sorry but i think that going through all the numbers is REALLY not efficient at all...

Commented:
sumant:
isn't ur code essentially equivalent to mine? (the U-R generation part?)

Commented:
Lychee:
You are right about the order remark.

I been thinking about a different approach:

make an array with M-1 1's and N-1 0's.
for example M=5, n=3:
111100
now DON'T count the array.
just run all PERMUTATIONS of it.
All Premutations ar leagle paths
(because the number of 1's and 0's remains...)

AND you don't do ANY extra work.

I think its the best one get for this problem.

Yair

Commented:
How to do permutations ?

take it as a challenge
(recursive definition...)

:-)

Commented:

pls read them... they're mostly about permutations =)... or whatever u choose to call them...

Commented:
To lychee, your U and R is just the notation I took that notation only what is wrong in it? My algo and program is original which is more important.
If the grid has 2 horiz lines i.e. one row and N vertical lines i.e. (N-1) columns then answer is (N-1) not 1.

Commented:
sumant:
sorry then... just that ur algo is about the same as mine... u can read my algo if u want and compare and see... :>

urm... what i mean by 1 row is 1 horizontal line (logical since travel is along lines)... like i take 3x3 in the qn to mean 3 rows and 3 cols...

so 1 row means 1 answer

Commented:
I have looked at all the comments and possible answers that you all have given. I have tested them all, and scrapdog's answer was the first one in the list that appears to answer the question.

Thank you all for your help. scrapdog, the points are yours.

Commented:
Thanks!

But I should mention that I made a typo above:

if (x+1) <= width then
traverse(x+1,y1);
if (y+1) <= height then
traverse(x,y+1);

The "y1" should be "y".  But I'm sure you've already figured that out.

Commented:
I also believe you made a mistake with:
if (x=width) and (y=height) then begin
for i := 1 to n do write('(',x_coordinates[i],
',',y_coordinates[i],') ');
writeln;
inc(count);

Shouldn't the x=width and y=height be <= instead? When I remove the diagonal movement code, the only point it prints is the final one. (the top right corner)

Besides that, everything else seems fine!

Commented:
Actually, it is supposed to be x=width and y=height, because if and only if this is true, the end of the path has been reached.  If you got it to work otherwise, however, I won't dispute it.

Commented:
Re: my last comment...

The typo wasn't changing the = to <= it was changing:
if (x+1) <= width then
traverse(x+1,y1);
if (y+1) <= height then
traverse(x,y+1);

to:
if (x+1) <= width then
inc(N);
traverse(x+1,y1);
dec(N);
if (y+1) <= height then
inc(N);
traverse(x,y+1);
dec(N);

Not sure if you're willing to help me with one more problem I'm having with your code...

You declare your array using [1..width+height] while width+height are constants... but when I change them to user defined variables, I can't seem to get it to work. Would it work if I declared the array in the procedure instead?

Commented:
>Would it work if I declared the array in the procedure instead?

Nope...the sizes of the array must be declared at compile-time.

This is an easy problem to fix though.  Change the constants to

const
max_width = (some number);
min_width = (some number);

then declare your array like this:

[1..max_width + max_height]

max_width and min_width are pretty self explanatory...they specify the upper limits that you will allow the user to enter.  The declaration will allocate the maximum number of bytes you will need for a grid max_width x max_height in any case.

Continue using width and height as variables, and the program should work correctly.

Commented:
to yairy
if it's a typo, then sorry me
peace to you...

Commented:
:-)
Unlock the solution to this question.

Experts Exchange is the only place where you can interact directly with leading experts in the technology field. Become a member today and access the collective knowledge of thousands of technology experts.