CHALLENGE: WALK ALONG THE GRID

Question

A classic Math Olympiad question: How many ways are there to go through an m-by-n grid by walking only up and right?

Let's implement that in code. Given that there is a grid of size m-by-n, print the number of ways to go from the bottom left to the top right corner by only moving up and right.
But we are not done yet. The challenge is too easy.
Let us include a list of forbidden points you cannot visit, with coordinates (x,y) relative to the start point.
Good luck!

Answer 1

🔰🔰🔰🔰🔰🔰🔰🔰🔰🔰🔰🔰🔰🔰🔰🔰🔰🔰🔰🔰🔰🔰🔰🔰🔰🔰
//btw sorry vengat ... no time for making code ... but i would like to give my mathematical answer ... a general answer

👉1) suppose u want to go from A (x,y) to B (l,m) ... //only move up amd right
then , l>=x & m>=y //obviously ☺

u need to move (l-x) ways to go right by 1 step & (m-y) steps to go down

therefore 👉👉👉 {(l+m)-(x+y)} ! / {(l-x)! . (m-y)!}
//basic method of bijection , //combinations ☺

👉2)A (x,y) to B (l,m) without C (e,f)

// check condition in 1) and also check whether C lies b/w way from A & B or not

👉👉👉answer in 1) - ((ways of going from A to C). (ways of going from C to B)
//use formula derived in 1)

👉3) A (x,y) to B (l,m) through pt. P (s,k)

👉👉👉3)(no. of ways from A to P ). (no. of ways from P to B)
//use formula derived in 1)

//🙋🙋🙋for more than 1 forbideen points 👍👍👍
for more than 1 forbidden points ... u need to substract ways of passing through these points

example ::: A to B & pt. C & D are forbidden points
then ,
(total no. of ways from pt. A to pt. B ) - { (ways from pt. A to pt. C)(ways from pt. C to pt. B) + (same for pt. D) + (ways from pt.A to pt. C )(ways from pt.C to pt.D). (ways from pt. D to pt. B)}

//hope u like the soln... , & happy coding☺☺☺

//bye bye tata 🌠

Answer 2

thnx 😊😊 @vengat , galaxy
//more xp earned by this post then challenges i took ☺

Answer 3

guys //just see my answer , no confusion be happy ☺

//& what u mean by 7×5 path ... might u mean from origin(@one corner) to opposite diagonal corner

answer will be 12! / 7!.5! without obstacles ☺ ie 792 //thats correct

Answer 4

yes

Answer 5

@kartikey

4C2 ie 6 ways

moving right and upward will only be possible if respective coordinates of pt.A are smaller or equal to respective coordinates of B

@yash
welcome // now everyone can code the challenge ☺ ... hahaha

Answer 6

haan cbse //thats agrawal ... waise agarwal hi thaa but 10th ma agrawal chala gaya thaa toh ab ma agrawal use karta hun 😂

Answer 7

i will give it a try //wait ☺

//but its too easy make it , for making it more good

for example ::: we need to walk from A(x,y) to pt. B(i,j) &
we need to find ...

1) find total no. ways of going from pt. A to pt. B (ie no restriction)
2)find total no. of ways of going from A to B without going to coordinates p (l,m)
3)find total no. of ways of going from A to B through pt. p (l,m)

//how about this ☺ @vengat

Answer 8

@yash ,

bhai yarr p, d block toh puche hi mat ... 1st term ma unhone band bajadi
aur ab 2nd term ma organic chemistry aa gayi 😑 but i am finding it some interesting ... but rxns learn karne ma meri band baj gayi ha

//par karni toh padegi kaise bhi ... best of luck 👍 to u ...
👉study chemistry hard

Answer 9

@Gaurav Agrawal It's good 😄😄

Answer 10

Sayan Nice job.
@Gaurav I gave you a little something for your explanation,

Answer 11

Nice work Sayan!
I particularly like Gaurav's explanation so I gave him 33XP

Answer 12

@Yash I just assumed that grid and asked the number of ways to reach 3 from 7..

Answer 13

@ vengat...
thanks...

Answer 14

@ vengat...

this code gives u no. of path to go from a start-point to an end-point..(only up / right)

bonus...** give any starting and ending point
** give more than 1 forbidden points
** default starting point is left bottom, default ending point is top right
** default list forbidden points is set to empty

## pass arguments in function as u want

## it results -1 if starting point is in left side or in bottom of end point..

https://code.sololearn.com/c7pui8yMCwUR/?ref=app

Answer 15

An interesting problem.

(There seems to be a slight difference of understanding as to whether an m x n grid has m rows and n columns from (1, 1) to (m, n) or m+1 rows and n+1 columns from (0, 0 to (m, n). I assume the latter.)

If there are no forbidden points the answer is simply the number of permutations of m rightward moves and n upward moves which is factorial(m+n)/(factorial(m)*factorial(n)).

If there is just one forbidden point the answer can be obtained by subtracting the number of routes through the forbidden point.

If there is more than one forbidden point the answer becomes very messy as you have to consider routes through all combinations of the forbidden points.

The alternative is to solve the problem for each point by first solving the problem for the point below and the point to the left and then add them which my program does.
If the input to
https://code.sololearn.com/cNwQxBj30TSc/#java
is:
7 5 2 3 6 4 4 1
the output is:
In a 7x5 grid without forbidden points
there are 792 ways
but with 3 forbidden points at
(2, 3) (4, 1) (6, 4)
there are just 187 ways.

Answer 16

123
456
789

If this is grid, how many ways are there to reach 3 from 7?

Answer 17

@Ga Yes but, Pegasus said that we can move only in right and up, so I just need an example.

Answer 18

https://code.sololearn.com/cH2EfcURkEWp/?ref=app

Answer 19

@ Gaurav
@ Vcc

7 * 5 grid...

{(7-1)*(5-1)} !
---------------- = 210
(7-1) ! * (5-1) !

i implemented this thinking a matrix...thats why subtracted 1#####

## its corrected now...thanks to u two

and....@ Vcc..
suppose its 1 * 1 grid..
means just like a box...
for forbidden points ony 0,0..
ur code shud give 1 way...of 2 ways...
its giving 0

Answer 20

Here is my code.
I'm not confident this is a right answer.
https://code.sololearn.com/cXD0Sl2skBE1/?ref=app