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

My paths from A to F would be: A - > B -> C -> F or A -> D -> E -> F or A ->B -> E - > F so on...

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

Thank you,

Answer 1

Answer:

import java.util.Stack;

class Main
{
        public static void findPaths(char[][] mat, Stack<Character> path,
                                                                 int i, int j)
        {
                int M = mat.length;
                int N = mat[0].length;

                // if we have reached the last cell, print the route
                if (i == M - 1 && j == N - 1)
                {
                        path.add(mat[i][j]);
                        System.out.println(path);
                        path.pop();

                        return;
                }

                // include current cell in path
                path.add(mat[i][j]);

                // move right
                if ((i >= 0 && i < M && j + 1 >= 0 && j + 1 < N)) {
                        findPaths(mat, path, i, j + 1);
                }

                // move down
                if ((i + 1 >= 0 && i + 1 < M && j >= 0 && j < N)) {
                        findPaths(mat, path, i + 1, j);
                }

                // remove current cell from path
                path.pop();
        }

        public static void main(String[] args)
        {
                char[][] mat =
                {
                        { 'A','B','C' },
                        { 'D','E','F' },
                };

                Stack<Character> path = new Stack<>();

                // start from (0, 0) cell
                int x = 0, y = 0;

                findPaths(mat, path, x, y);
        }
}

Output:

Please give thumbsup, or do comment in case of any query. Thanks.