Question

How can I return in a list all possible paths from a grid if I can only go right and down?

For example consider the following table:

A B C

D E F

If I go right I need to insert in my list 'H' if I go down I need to insert in my list 'V'.

For example the path A - > B -> C -> F would be H - H - V

The path A -> D -> E -> F would be V - H - H

How would be the code for that? Please preference write in JAVA.

Thank you,

Answer 1

Complete code in JAVA:-

import java.util.*;

// Main class
class Path {

   // 'move' method takes next possible move in either of the direction from 'i', 'j'
   // move horizontally or vertically.
   public static void move(String path, char [][]mat, int i, int j, int n, int m, ArrayList<String> lists) {

       // Adding current character into path
       path = (path+mat[i][j]+"->");

       // This variable will keep track if there is further a move possible or not.
       boolean canMove = false;

       // If possible move vertically.
       if(i < n-1) {
           move(path, mat, i+1, j, n, m, lists);
           canMove = true;
       }

       // If possible move horizontally.
       if(j < m-1) {
           move(path, mat, i, j+1, n, m, lists);
           canMove = true;
       }

       // If no further move was possible
       // 'path' is one possible path, so add it to 'lists'.
       if(!canMove) {
           lists.add(path.substring(0, path.length()-2));
       }
   }

   // Main function.
   public static void main(String ... args) {

       // This is the matrix in which we have to find all possible paths.
       char [][]mat = new char[2][3];
       mat[0][0] = 'A';
       mat[0][1] = 'B';
       mat[0][2] = 'C';
       mat[1][0] = 'D';
       mat[1][1] = 'E';
       mat[1][2] = 'F';

       // 'paths' list will store all possible paths.
       ArrayList<String> paths = new ArrayList<String> ();

       // Exploring all possible paths.
       String path = "";
       move(path, mat, 0, 0, 2, 3, paths);

       // Print all the possible paths.
       System.out.println("All possible paths : ");
       for(int i = 0; i < paths.size(); i++) {
           System.out.println(paths.get(i));
       }
   }
}

Screenshot of output:-