Skip to content

Instantly share code, notes, and snippets.

@mkell85
Created November 7, 2018 15:32
Show Gist options
  • Save mkell85/f10281bd9741af224d7592cfc244ded1 to your computer and use it in GitHub Desktop.
Save mkell85/f10281bd9741af224d7592cfc244ded1 to your computer and use it in GitHub Desktop.
Dynamic Programming to count paths with blockages
import java.util.Arrays;
class Path {
static boolean isValidPosition(boolean[][] board, int row, int col) {
if(row >= board.length || col >= board.length)
return false;
return board[row][col];
}
static boolean isEndPosition(boolean[][] board, int row, int col) {
return row == board.length - 1 && col == board.length - 1;
}
static int countPath(boolean[][] board, int row, int col) {
if(!isValidPosition(board, row, col)) {
return 0;
}
if(isEndPosition(board, row, col)) {
return 1;
}
return countPath(board, row + 1, col) + countPath(board, row, col + 1);
}
public static void main(String[] args) {
// boolean[][] board = new boolean[][] {
// { true, true, false, true, true},
// { true, true, true, true, false},
// { true, false, true, true, true},
// { true, true, false, true, true},
// { true, true, true, true, true}
// };
boolean[][] board = {
{ true, true, true},
{ true, true, true},
{ true, true, true}
};
int paths = countPath(board, 0, 0);
System.out.printf("The number of paths are: %d", paths);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment