Reputation: 404
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
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
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
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