The number of paths in the matrix

Question

A pxq given a size matrix, and an axb size matrix is ​​removed from the upper right corner. Find the common number. paths from upper left to lower right, only movement on the right and down is allowed. No path should go to the remote matrix.

eg, -

  _ |_|_ |_|_| 

this is the (2x2) matrix after removing the (1x1) matrix in the upper right corner. no. 5 ways.

I can find out the total number of paths, but the method that I am going to eliminate the paths that enter the remote part is very elementary and therefore not effective.

So, is there a better algorithm for this?

Answer 1

You can use the grid structure:

The number of paths from one corner to another on a square grid is determined by the grid size of the Pascal triangle: (x+y) choose x

Each path must cross exactly one point on each diagonal.

Take all the points on the diagonal passing through the inner corner, calculate the number of paths through each and summarize.

This leads to the O(min(pa, qb)) algorithm, which assumes constant arithmetic.

In your case: (two paths to the center) * (two paths from the center) + (one path in the corner) = (four paths in the center) + (one path in 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 

Answer 2

Do a topological sort in the DAG ¹ representing the problem.

Then go from the last (receiver) to the first (source):

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

The complexity is linear in the size of the graph (iteration of each vertex exactly once) (using the dimensions of the matrix O(p*qa*b) )

---

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

 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) } 

Answer 3

 //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); }