Count the number of ways to traverse a 2D array
NumberWays.javapublic static int numberOfWays(int n, int m) {
if (n < m) {
int temp = n;
n = m;
m = temp;
}
int[] A = new int[m];
for (int j = 0; j < m; ++j) {
A[j] = 1;
}
for (int i = 1; i < n; ++i) {
int prev_res = 0;
for (int j = 0; j < m; ++j) {
A[j] = A[j] + prev_res;
prev_res = A[j];
}
}
return A[m - 1];
}
NumberWaysObstacles.java
// Given the dimensions of A, n and m, and B, return the number of ways
// from A[0][0] to A[n - 1][m - 1] considering obstacles.
public static int numberOfWaysWithObstacles(int n, int m,
List<List<Boolean>> B) {
int[][] A = new int[n][m];
if (B.get(0).get(0)) { // No way to start from (0, 0) if B[0][0] == true.
return 0;
}
A[0][0] = 1;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (!B.get(i).get(j)) {
A[i][j] += (i < 1 ? 0 : A[i - 1][j]) + (j < 1 ? 0 : A[i][j - 1]);
}
}
}
return A[n - 1][m - 1];
}
