Find the number of paths in a table

Question

Tere - R × C size table; R rows and columns C. Under the rectangle of the table is locked. We can move straight or down. What is the number of paths from the upper left cell to the lower right cell, and not skip the locked sub-rectangle?

My approach: Calculate the path from the lines r2 C = {0 to c1-1} and the paths from the string r1 C = {c2 + 1, C}

r1, c1, r2 and c2, the upper left cell and the lower right cell of the locked rectangle.

Cal Calculate C(n,k) 

My code is:

 int R = in.nextInt()-1; int C = in.nextInt()-1; int r1 = in.nextInt()-1; int c1= in.nextInt()-1; int r2 = in.nextInt()-1; int c2 = in.nextInt()-1; long ans=0; long temp=0; temp+= Cal(R-r2+C-c1,C-c1); for(int i=0;i<c1 && r2!=R;i++){ ans+=Cal(i+r2,r2)*(Cal(R-r2+Ci,Ci)-temp); } temp=0; temp+=Cal(r1+c2,r1); for(int i=c2+1;i<=C;i++){ ans+= (Cal(i+r1,r1)-temp)*Cal(C-i+R-r1,Ci); } System.out.println(ans); 

I am not getting the correct answer for my algorithm. Please help me if I do something wrong.

 Sample input: 8 12 5 5 8 8 ANS:7008 

Answer 1

I suggest using a dynamic programming method to solve this problem. Each “unlocked” cell on the board will have a number associated with it, the number of ways to get to the lower right; this is currently an undefined number in each cell.

It is best to explain this with an example. Let's pretend that

  OOOOOO
 OXXOOO
 OXXOOO
 OOOOOO
 OOOOOO

as our board, where X is an obstacle and O is the square into which we have not yet completed the number of paths in the lower right corner. Now we are working from the lower right corner back. We will start by filling in the number 1 in the lower right corner, although this may not make a general sense.

  OOOOOO
 OXXOOO
 OXXOOO
 OOOOOO
 OOOOO1

Now the two squares closest to the lower right can be filled. They are light.

  OOOOOO
 OXXOOO
 OXXOOO
 OOOOO1
 OOOO11

Now we can fill in 3 more squares:

  OOOOOO
 OXXOOO
 OXXOO1
 OOOO21
 OOO111

In each case, what we do is simply add the number to the right of the square and the number below the square, where we assume that the zeros will be on the right and bottom sides of the board. The next step:

  OOOOOO
 OXXOO1
 OXXO31
 OOO321
 Oo1111

So far, we have obtained binomial coefficients, what we expect in such a problem. The next step:

  OOOOO1
 OXXO41
 OXX631
 OO4321
 O11111

More binomial coefficients. The next step:

  OOOO51
 OXXA41
 OXX631
 O54321
 111111

I use the letter A for 10. This is like binomial coefficients, but we are missing a few tips. However, this will change soon. The next step:

  OOOF51
 OXXA41
 OXX631
 654321
 111111

Notice the use of F for 15. Now everything is getting interesting. Since we cannot go through the obstacle, we map 0 to the cells in the obstacle. To fill the gap in the upper right corner, add F + 0 = F. Similarly, 0 + 6 = 6.

  OOFF51
 OXXA41
 6XX631
 654321
 111111

The next step:

  OFFF51
 6XXA41
 6XX631
 654321
 111111

Last step:

  UFFF51
 6XXA41
 6XX631
 654321
 111111

Here I use U for 21 = F + 6. This is the answer to the question.

This procedure works in general. We can fill in any cell for which we know the numbers on the right and below, and gradually fill the entire rectangle.

Answer 2

It's hard for me to understand the description of your algorithm, so I'm not sure how to handle this. However, I think one way to find the number of paths might be to subtract those paths that include cells in the sub-rectangle from all possible paths.

The number of paths that contain a specific cell is equal to the number of paths from the upper left corner to this cell, multiplied by the number of paths from this cell to the lower right. And since you can only move down or to the right, all this is enough to account for the left column and the top row of the sub-rectangle.

If you started in the upper left corner of a sub-rectangle, you can continue, as in the following example ( ABCDEF make up a sub-rectangle):

 start XXXX XABCX XDEFX XXXX end The sum of paths that include A,B,C,D,E or F equals: Paths to A * Paths from A to end = 2 choose 1 * 5 choose 2 = 20 + (Paths to cell above B) * Paths from B to end = 1 * 4 choose 2 = 6 + (Paths to cell above C) * Paths from C to end = 1 * 3 choose 1 = 3 + (Paths to cell left of D) * Paths from D to end = 1 * 4 choose 1 = 4 Solution equals: total paths - the number of paths that include A,B,C,D,E or F = 7 choose 3 - (20 + 6 + 3 + 4) = 2 

JavaScript Code:

 function f(Rows,Cols,r1,c1,r2,c2){ var r = Rows - r1, total = C(Rows + Cols - 2,Rows - 1), s = C(r1 + c1 - 2,r1 - 1) * C(Cols - c1 + r,r); if (c2 > c1 && r1 > 1){ for (var i=c1+1; i<=c2; i++){ s += C(i + r1 - 3,i - 1) * C(Cols - i + r,r); } } if (r2 > r1 && c1 > 1){ for (var i=r1+1; i<=r2; i++){ s += C(i + c1 - 3,i - 1) * C(Rows - i + Cols - c1,Rows - i); } } return total - s; } function C(n,k){if(k==0||n==k)return 1;var p=n;for(var i=2;i<=k;i++)p*=(n+1-i)/i;return p} 

Conclusion:

 console.log(f(4,5,2,2,3,4)); 2 console.log(f(5,6,2,2,3,3)); 21 console.log(f(8,12,5,5,8,8)); 7008