Number of paths in a matrix

Question

A p x q size matrix is given, and a matrix of size a x b is removed from top right corner. Find the total no. of paths from top left to bottom right, with only right and down movements allowed. No path should go into the removed matrix.

eg-

 _
|_|_
|_|_|

this is (2x2) matrix after removing (1x1) matrix from top right corner. no. of ways - 5.

I am able to find out the total number of paths, but the method I am thinking of eliminating the paths that go into the removed portion is very elementary and hence not efficient.

So, are there any better algorithm for it ?

Answer 1

You can exploit the structure of the grid:

The number of paths from one corner to the other on a square grid is given by the size of the grid by the pascal's triangle: (x+y) choose x

Each path must cross exactly one point on each diagonal.

Take all points on the diagonal that passes through the inner corner, calculate the number of paths through each, and sum.

This leads to an O(min(p-a, q-b)) algorithm assuming constant-time arithmetic.

In your case: (two paths to the center) * (two paths from the center) + (one path through the corner) = (four paths through the center) + (one path through the corner) = (five paths)

+-+-+
| | |
+-+-A-+-+
| | | | |
+-B-+-+-+
| | | | |
C-+-+-+-+
| | | | |
+-+-+-+-+

  (1+2) choose 1 * (2+3) choose 2 (through A)
+ (2+1) choose 2 * (3+2) choose 3 (through B)
+ (3+0) choose 3 * (4+1) choose 4 (through C)

= 3 choose 1 * 5 choose 2
+ 3 choose 2 * 5 choose 3
+ 3 choose 3 * 5 choose 4

= 3*10
+ 3*10
+ 1*5

= 30+30+5 = 65 paths