Thursday 30 January 2014

Print all possible paths from top left to bottom right of a mXn matrix

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
t> UA-39527780-1 back to top