Print all paths from top left to bottom right of MxN matrix

ghz 10months ago ⋅ 114 views

To print all paths from the top-left corner to the bottom-right corner of an MxN matrix, you can use a depth-first search (DFS) algorithm. Here's a Java implementation:

import java.util.ArrayList;
import java.util.List;

public class AllPathsInMatrix {

    public static List<List<Integer>> allPaths(int[][] matrix) {
        List<List<Integer>> paths = new ArrayList<>();
        List<Integer> currentPath = new ArrayList<>();
        dfs(matrix, 0, 0, currentPath, paths);
        return paths;
    }

    private static void dfs(int[][] matrix, int row, int col, List<Integer> currentPath, List<List<Integer>> paths) {
        int m = matrix.length;
        int n = matrix[0].length;

        // Add the current cell to the current path
        currentPath.add(matrix[row][col]);

        // If reached the bottom-right corner, add the current path to the list of paths
        if (row == m - 1 && col == n - 1) {
            paths.add(new ArrayList<>(currentPath));
        } else {
            // Move right if within bounds
            if (col + 1 < n) {
                dfs(matrix, row, col + 1, currentPath, paths);
            }
            // Move down if within bounds
            if (row + 1 < m) {
                dfs(matrix, row + 1, col, currentPath, paths);
            }
        }

        // Remove the current cell from the current path (backtrack)
        currentPath.remove(currentPath.size() - 1);
    }

    public static void main(String[] args) {
        int[][] matrix = {
            {1, 2, 3},
            {4, 5, 6},
            {7, 8, 9}
        };
        List<List<Integer>> paths = allPaths(matrix);

        System.out.println("All paths from top-left to bottom-right:");
        for (List<Integer> path : paths) {
            System.out.println(path);
        }
    }
}

In this implementation:

  • We use depth-first search (DFS) to traverse all possible paths from the top-left corner to the bottom-right corner of the matrix.
  • The dfs method explores all valid directions (right and down) from the current cell recursively.
  • When reaching the bottom-right corner, the current path is added to the list of paths.
  • We initialize an empty list to store all paths and an empty list for the current path.
  • We call the dfs method to start the depth-first search from the top-left corner.
  • We test the implementation with an example matrix and print all generated paths.
#algorithm