Print all possible paths from top left to bottom right of a mXn matrix | GeeksforGeeks
The problem is to print all the possible paths from top left to bottom right of a mXn matrix with the constraints that from each cell you can either move only to right or down.
Java code:
https://github.com/mission-peace/interview/blob/master/src/com/interview/recursion/PrintAllPathFromTopLeftToBottomRight.java
public void print(int arr[][],int row, int col,int result[],int pos){
if(row == arr.length-1 && col == arr[0].length-1){
result[pos] = arr[row][col];
printArray(result);
return;
}
if(row >= arr.length || col >= arr[0].length){
return;
}
result[pos] = arr[row][col];
print(arr,row,col+1,result,pos+1);
print(arr,row+1,col,result,pos+1);
}
http://opensourceforgeeks.blogspot.com/2014/01/print-all-possible-paths-from-top-left.html
public class AllPathsPrinter {
int [][] array;
int rowCount;
int colCount;
public AllPathsPrinter(int [][]array){
this.array = array;
rowCount = array.length;
colCount = array[0].length;
}
public void printAllPaths(int currX, int currY, String path){
if(currX == rowCount-1){
for(int j=currY;j<=colCount-1;j++){
path = path + array[currX][j];
}
System.out.println("Path : " + path);
return;
}
if(currY == colCount-1){
for(int i=currX;i<=rowCount-1;i++){
path = path + array[i][currY];
}
System.out.println("Path : " + path);
return;
}
path = path + array[currX][currY];
printAllPaths(currX+1, currY, path);
printAllPaths(currX, currY+1, path);
}
}
Count all possible paths from top left to bottom right of a mXn matrix
https://github.com/mission-peace/interview/blob/master/src/com/interview/recursion/PrintAllPathFromTopLeftToBottomRight.java
public class PrintAllPathFromTopLeftToBottomRight {
public void print(int arr[][],int row, int col,int result[],int pos){
if(row == arr.length-1 && col == arr[0].length-1){
result[pos] = arr[row][col];
printArray(result);
return;
}
if(row >= arr.length || col >= arr[0].length){
return;
}
result[pos] = arr[row][col];
print(arr,row,col+1,result,pos+1);
print(arr,row+1,col,result,pos+1);
}
public static void main(String args[]){
PrintAllPathFromTopLeftToBottomRight pam = new PrintAllPathFromTopLeftToBottomRight();
int arr[][] = {{1,2,3,4},{5,6,7,8},{9,10,11,12}};
int result[] = new int[arr.length + arr[0].length-1];
pam.print(arr, 0, 0, result,0);
}
}
http://algorithms.tutorialhorizon.com/dynamic-programming-count-all-paths-in-2d-matrix-with-obstructions-in-it/
http://algorithms.tutorialhorizon.com/dynamic-programming-count-all-paths-from-top-left-to-bottom-right-of-a-mxn-matrix/
Read full article from Print all possible paths from top left to bottom right of a mXn matrix | GeeksforGeeks
The problem is to print all the possible paths from top left to bottom right of a mXn matrix with the constraints that from each cell you can either move only to right or down.
/* mat: Pointer to the starting of mXn matrix i, j: Current position of the robot (For the first call use 0,0) m, n: Dimentions of given the matrix pi: Next index to be filed in path array *path[0..pi-1]: The path traversed by robot till now (Array to hold the path need to have space for at least m+n elements) */void printAllPathsUtil(int *mat, int i, int j, int m, int n, int *path, int pi){ // Reached the bottom of the matrix so we are left with // only option to move right if (i == m - 1) { for (int k = j; k < n; k++) path[pi + k - j] = *((mat + i*n) + k); for (int l = 0; l < pi + n - j; l++) cout << path[l] << " "; cout << endl; return; } // Reached the right corner of the matrix we are left with // only the downward movement. if (j == n - 1) { for (int k = i; k < m; k++) path[pi + k - i] = *((mat + k*n) + j); for (int l = 0; l < pi + m - i; l++) cout << path[l] << " "; cout << endl; return; } // Add the current cell to the path being generated path[pi] = *((mat + i*n) + j); // Print all the paths that are possible after moving down printAllPathsUtil(mat, i+1, j, m, n, path, pi + 1); // Print all the paths that are possible after moving right printAllPathsUtil(mat, i, j+1, m, n, path, pi + 1); // Print all the paths that are possible after moving diagonal // printAllPathsUtil(mat, i+1, j+1, m, n, path, pi + 1);}// The main function that prints all paths from top left to bottom right// in a matrix 'mat' of size mXnvoid printAllPaths(int *mat, int m, int n){ int *path = new int[m+n]; printAllPathsUtil(mat, 0, 0, m, n, path, 0);}Java code:
https://github.com/mission-peace/interview/blob/master/src/com/interview/recursion/PrintAllPathFromTopLeftToBottomRight.java
public void print(int arr[][],int row, int col,int result[],int pos){
if(row == arr.length-1 && col == arr[0].length-1){
result[pos] = arr[row][col];
printArray(result);
return;
}
if(row >= arr.length || col >= arr[0].length){
return;
}
result[pos] = arr[row][col];
print(arr,row,col+1,result,pos+1);
print(arr,row+1,col,result,pos+1);
}
http://opensourceforgeeks.blogspot.com/2014/01/print-all-possible-paths-from-top-left.html
public class AllPathsPrinter {
int [][] array;
int rowCount;
int colCount;
public AllPathsPrinter(int [][]array){
this.array = array;
rowCount = array.length;
colCount = array[0].length;
}
public void printAllPaths(int currX, int currY, String path){
if(currX == rowCount-1){
for(int j=currY;j<=colCount-1;j++){
path = path + array[currX][j];
}
System.out.println("Path : " + path);
return;
}
if(currY == colCount-1){
for(int i=currX;i<=rowCount-1;i++){
path = path + array[i][currY];
}
System.out.println("Path : " + path);
return;
}
path = path + array[currX][currY];
printAllPaths(currX+1, currY, path);
printAllPaths(currX, currY+1, path);
}
}
Count all possible paths from top left to bottom right of a mXn matrix
// Returns count of possible paths to reach cell at row number m and column// number n from the topmost leftmost cell (cell at 1, 1)int numberOfPaths(int m, int n){ // Create a 2D table to store results of subproblems int count[m][n]; // Count of paths to reach any cell in first column is 1 for (int i = 0; i < m; i++) count[i][0] = 1; // Count of paths to reach any cell in first column is 1 for (int j = 0; j < n; j++) count[0][j] = 1; // Calculate count of paths for other cells in bottom-up manner using // the recursive solution for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) // By uncommenting the last part the code calculatest he total // possible paths if the diagonal Movements are allowed count[i][j] = count[i-1][j] + count[i][j-1]; //+ count[i-1][j-1]; } return count[m-1][n-1];}
Note the count can also be calculated using the formula (m-1 + n-1)!/(m-1)!(n-1)!. See this for more details.
int numberOfPaths(int m, int n){ // If either given row number is first or given column number is first if (m == 1 || n == 1) return 1; // If diagonal movements are allowed then the last addition // is required. return numberOfPaths(m-1, n) + numberOfPaths(m, n-1); // + numberOfPaths(m-1,n-1);}public class PrintAllPathFromTopLeftToBottomRight {
public void print(int arr[][],int row, int col,int result[],int pos){
if(row == arr.length-1 && col == arr[0].length-1){
result[pos] = arr[row][col];
printArray(result);
return;
}
if(row >= arr.length || col >= arr[0].length){
return;
}
result[pos] = arr[row][col];
print(arr,row,col+1,result,pos+1);
print(arr,row+1,col,result,pos+1);
}
public static void main(String args[]){
PrintAllPathFromTopLeftToBottomRight pam = new PrintAllPathFromTopLeftToBottomRight();
int arr[][] = {{1,2,3,4},{5,6,7,8},{9,10,11,12}};
int result[] = new int[arr.length + arr[0].length-1];
pam.print(arr, 0, 0, result,0);
}
}
http://algorithms.tutorialhorizon.com/dynamic-programming-count-all-paths-in-2d-matrix-with-obstructions-in-it/
Objective: Given two dimensional matrix, write an algorithm to count all possible paths from top left corner to bottom-right corner. You are allowed to move only in two directions, move right OR move down. There are few obstructions as well, means few cells are blocked and you cannot travel that cell.
public int count(int [][] arrA, int row, int col){
//base case
//check if last row OR column is reached since after that only one path
if(row==arrA.length-1 && col==arrA.length-1){
return 1;
}
int left =0;
int down = 0;
if(row!=arrA.length-1 && arrA[row+1][col]!=-1){
left = count(arrA, row+1, col);
}
if(col!=arrA.length-1 && arrA[row][col+1]!=-1){
down = count(arrA, row, col+1);
}
return left + down;
}
public int countDP(int [][] arrA){
int result [][] = arrA;
for (int i = 1; i <result.length ; i++) {
for (int j = 1; j <result.length ; j++) {
if(result[i][j]!=-1){
result[i][j]=0;
if(result[i-1][j]>0)
result[i][j]+=result[i-1][j];
if(result[i][j-1]>0)
result[i][j]+=result[i][j-1];
}
}
}
return result[arrA.length-1][arrA.length-1];
}
http://algorithms.tutorialhorizon.com/dynamic-programming-count-all-paths-from-top-left-to-bottom-right-of-a-mxn-matrix/
Objective: Given two dimensional matrix, write an algorithm to count all possible paths from top left corner to bottom-right corner. You are allowed to move only in two directions, move right OR move down.
public int count(int [][] arrA, int row, int col){
//base case
//check if last row OR column is reached since after that only one path
//is possible to reach to the bottom right corner.
if(row==arrA.length-1 || col==arrA.length-1){
return 1;
}
return count(arrA, row+1, col) + count(arrA, row, col+1);
}
public int countDP(int [][] arrA){
int result [][] = new int[arrA.length][arrA.length];
//base case: if we have one cell then there is only one way
result[0][0] = 1;
//no of paths to reach in any cell in first row = 1
for (int i = 0; i <result.length ; i++) {
result[0][i] = 1;
}
//no of paths to reach in any cell in first col = 1
for (int i = 0; i <result.length ; i++) {
result[i][0] = 1;
}
for (int i = 1; i <result.length ; i++) {
for (int j = 1; j <result.length ; j++) {
result[i][j] = result[i-1][j] + result[i][j-1];
}
}
return result[arrA.length-1][arrA.length-1];
}
