Question :
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.(GeeksForGeeks)
Idea :
The algorithm is a simple recursive algorithm, from each cell first
print all paths by going down and then print all paths by going right.
Do this recursively for each cell encountered.
Solution :
/** * Created with IntelliJ IDEA. * User: aniket * Date: 30/1/14 * Time: 4:39 PM * To change this template use File | Settings | File Templates. */ 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); } public static void main(String args[]){ int [][] ar = new int[][]{{1, 2, 3}, {4, 5, 6}}; AllPathsPrinter allPathsPrinter = new AllPathsPrinter(ar); allPathsPrinter.printAllPaths(0,0,""); } }
Output :
Path : 1456
Path : 1256
Path : 1236
Path : 1256
Path : 1236
No comments:
Post a Comment