Number of paths in a grid (lattice) graph

Question

I am trying to solve a variant of the very popular question in which we find the number of distinct valid paths on a directed graph. The graph's nodes make up a m x n lattice (grid), and the edges only lead down and right. The goal is to find how many distinct paths start at the top left corner of and end in the bottom right.

So one possible path might be down m, right n.

In this variant of the problem, there is a complication. A rectangular area inside the lattice is blocked -- no paths can go through it. (The edges that would normally lead to these nodes don't exist)

I am using Dynamic Programming to solve with a time complexity of \$O(m*n)\$.

It works pretty good with small value for rows and columns but for bigger values it throws OutOfMemoryError.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class GeekForGeeks{
public static void main(String[] args) throws NumberFormatException,
 IOException {
 // TODO Auto-generated method stub
 BufferedReader inp = new BufferedReader(
 new InputStreamReader(System.in));
 String[] s1 = inp.readLine().split(" ");
 int row = Integer.parseInt(s1[0]);
 int col = Integer.parseInt(s1[1]); // Input for the value of row &
 // col
 String[] s2 = inp.readLine().split(" ");
 int r1 = Integer.parseInt(s2[0]);
 int c1 = Integer.parseInt(s2[1]);
 int r2 = Integer.parseInt(s2[2]);
 int c2 = Integer.parseInt(s2[3]); // Input for the value of row &
 // column of blocked path
 int[][] A = new int[row][col];
 for (int i = 0; i < row; i++)
 for (int j = 0; j < col; j++)
 A[i][j] = 1;
 for (int i = r1 - 1; i < r2; i++)
 for (int j = c1 - 1; j < c2; j++)
 A[i][j] = 0;
 int answer = numOfPaths(A, row, col);
 System.out.println(answer);
 }
}
private static int numOfPaths(int A[][], int row, int col) {
 long mod = (long) Math.pow(10, 9) + 7;
 int[][] B = new int[row][col]; // new matrix to store number of paths
 // if starting point blocked then no path is there to reach right down
 if (A[0][0] == 0) {
 return 0;
 } else {
 int i, j;
 for (i = 0; i < col; i++) {
 if (A[0][i] == 0)
 break; // exit from the for loop, and set remaining elements
 // the first row set to ZERO
 B[0][i] = A[0][i];
 }
 while (i < col)
 B[0][i++] = 0; // When any starting row is blocked then all the
 // row down will also be blocked and
 // have no path to be reached from starting
 // point.
 for (i = 1; i < row; i++) {
 if (A[i][0] == 0)
 break;// exit from the for loop, and set remaining elements
 // in the first column set to ZERO
 B[i][0] = A[i][0];
 }
 while (i < row)
 B[i++][0] = 0; // When any column is blocked all starting column
 // towards right will be blocked
 for (i = 1; i < row; i++)
 for (j = 1; j < col; j++)
 if (A[i][j] != 0)
 B[i][j] = (int) (((B[i - 1][j] % mod) + (B[i][j - 1] % mod)) % mod);
 // otherwise, we enter the sum of the value above and left
 return B[row - 1][col - 1]; // return the last column and row.
 }
}

• wei2912: Could you give more details on the problem?
• arqam: @wei2912 what details you want?
• wei2912: The edited version provides the details I need.

Answer 1

It works pretty good with small value for rows and columns but for bigger values it throws OutOfMemoryError.

That's hard to believe as I can't see any allocation there besides new int[row][col], which is no problem unless the dimensions get much bigger than a few thousands. I guess they do and you'll need a smarter algorithm. As the whole computation runs top-down, you don't have to store the whole matrix. A single row should do.

// TODO Auto-generated method stub

Are you sure you need it???

String[] s1 = inp.readLine().split(" ");
int row = Integer.parseInt(s1[0]);
int col = Integer.parseInt(s1[1]); //Input for the value of row & col

Inline comments are fine as long as they belong to the command in their line. But this is a block comment and should precede the block. It could be a also a comment for s1, but not col.

int r1 = Integer.parseInt(s2[0]);

Are we supposed to guess what r1 means? What about naming it topLeft?

private static int numOfPaths(int A[][], int row,int col)
{

Java uses "Egyptian brackets" (no line break before the opening brace). There should be a space after every comma. Passing row and col is redundant as they're obtainable from A.

if( A[0][0] == 0)

Spacing! I doubt that this special case handling is necessary.

{
 return 0;
}
else
{

The nice thing about "early return" is that it allows you to handle special cases upfront without increasing the nesting depth. Your "else" after "return" is wrong.

int i,j;
for(i=0; i<col; i++)

Use for (int i=...) instead, so that the scope of every variable is as small as possible.

if( A[0][i] == 0 )
 break; // exit from the for loop, and set remaining elements the first row set to ZERO
 B[0][i] = A[0][i];

Spacing! So you first exit the loop and then (inside of the loop) set the remaining part to zero? This can't work.

But you're lucky as all int array elements are initialized to zero anyway.

I guess all what's needed is

for (i = 1; i < row; i++) {
 for (j = 1; j < col; j++) {
 if (A[i][j] != 0) {
 B[i][j] = (int) (((B[i - 1][j] % mod) + (B[i][j - 1] % mod)) % mod);
 }
 }
}

Note the formatting (done by Eclipse for free). Also note that it's recommended to always use braces (you know "goto-fail", right?).

• arqam: yeah my matrix size is more than 1000, but then can we use a single row as you pointed out, because I am calculating the value from the column above and column left.
• maaartinus: @arqam Seriously, you're saying that you need one row above the current one. This together are two rows. Not the whole matrix.