CODEWITHSUNDEEP
algorithmmathcombinatorics
aclap
aclap

Reputation: 404

Number of paths in a matrix

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 ?

Upvotes: 7

Views: 3293

Answers (3)

murali kurapati
murali kurapati

Reputation: 1586

//assume we are moving from m,n to 1,1
int  numberOfPaths(int m, int n)
{
/*If the m,n  is left-bordered to the removed matrix, then move only downwards 
  till the end of removed matrix,then we can move in two directions*/
 //l1=numberOfrows(bigMatrix)-numberOfRows(smallMatrix), similarly l2 for columns
 if(m==l1&&n>=l2)
   return numberOfPaths(l1-1,l2+2)+numberOfPaths(l1,l2+1);
// If either given row number is first or given column number is first
if (m == 1 || n == 1)
    return 1;

 return  numberOfPaths(m-1, n) + numberOfPaths(m, n-1); 
}

Upvotes: 0

John Dvorak
John Dvorak

Reputation: 27317

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

Upvotes: 9

amit
amit

Reputation: 178521

Do a topological sort on the DAG1 representing the problem.

Then iterate from last (sink) to first (source):

f(v) = Sum(f(u)) for each (v,u) in E
base: f(sink) = 1

Complexity is linear in the size of the graph (iterating each vertex exactly once) (Using the dimensions of the matrix it is O(p*q-a*b))

(1) The graph G=(V,E) is:

V = { (i,j) | for each i,j in the matrix that was not deleted }
E = { ((i1,j1),(i2,j2)) | (i1,j1) is to the left/up of (i2,j2) }

Upvotes: 6

Related Questions