Finding the Number of paths in a table

Question

Tere is a table of size R×C; R rows and C columns. A sub-rectangle of the table is blocked. We are only able to move right or down. What is the number of paths from the upper-left cell to the lower-right cell while not passing the blocked sub-rectangle?

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

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

Cal Calculate C(n,k)

My Code:

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+C-i,C-i)-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,C-i);

}
System.out.println(ans);

I am not getting the correct answer for my above algorithm. Please Help me if i am doing something Wrong.

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

Answer 1

I suggest a dynamic programming approach to solving this problem. Each "unblocked" cell in the board will have a number associated with it, the number of ways of getting to the bottom right; currently that number is undefined in every cell.

It might be best to explain this with an example. Suppose we have

OOOOOO
OXXOOO
OXXOOO
OOOOOO
OOOOOO

as our board, where X represents an obstacle and O is a square into which we have not yet filled the number of paths to the bottom right. We now work from the bottom right corner backwards. We'll start by filling in the number 1 in the bottom right, although that might not make total sense.

OOOOOO
OXXOOO
OXXOOO
OOOOOO
OOOOO1

Now the two squares closest to the bottom right can be filled in. They're easy.

OOOOOO
OXXOOO
OXXOOO
OOOOO1
OOOO11

Now we can fill in 3 more squares:

OOOOOO
OXXOOO
OXXOO1
OOOO21
OOO111

In each case what we are doing is just adding together the number to the right of a square and the number below a square, where we imagine zeros to be off the right and bottom sides of the board. Next step:

OOOOOO
OXXOO1
OXXO31
OOO321
OO1111

So far, we're getting the binomial coefficients, which is what we'd expect in a problem like this. Next step:

OOOOO1
OXXO41
OXX631
OO4321
O11111

More binomial coefficients. Next step:

OOOO51
OXXA41
OXX631
O54321
111111

I'm using the letter A for 10. It's like the binomial coefficients but we're missing a few off the board. Soon that will change, however. Next step:

OOOF51
OXXA41
OXX631
654321
111111

Note the use of F for 15. Now things get interesting. Since we can't pass through the obstacle, we associate 0 with the cells in the obstacle. To fill in the blank at the top right, we add F + 0 = F. Similarly, 0 + 6 = 6.

OOFF51
OXXA41
6XX631
654321
111111

Next step:

OFFF51
6XXA41
6XX631
654321
111111

Last step:

UFFF51
6XXA41
6XX631
654321
111111

Here I'm using U for 21 = F + 6. That's the answer to the question.

The procedure works in general. We can fill in any cell for which we know the numbers to the right and below, and gradually we fill in the whole rectangle.