/**
 * 2D matrix, with obstacles (-1), empty cell(0), and packages(positive #)
 * and a set of packages(integer id).
 * Starting from (0,0), find the path to pick up all packages.
 */
public class FindPathForPackages {
    private static class Point{
        int x, y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public String toString() {
            return "{" + x + ", " + y + '}';
        }
    }

    List<List<Point>> paths = new ArrayList<>();

    List<List<Point>> findPath(int[][] M, Set<Integer> pkgs) {
        int row = M.length;
        int col = M[0].length;
        boolean[][] V = new boolean[row][col];

        helper(M, 0, 0, pkgs, V, new ArrayList<>());

        return paths;
    }

    private void helper(int[][] M, int x, int y, Set<Integer> pkgs, boolean[][] V, List<Point> cur) {
        if (pkgs.contains(M[x][y])) {
            pkgs.remove(M[x][y]);
            if (pkgs.isEmpty()) {
                paths.add(new ArrayList<>(cur));
                return;
            }
        }
        V[x][y] = true;
        int[] dx = {0, 0, 1, -1};
        int[] dy = {1, -1, 0, 0};

        for(int k = 0; k < 4; k++) {
            int xx = dx[k] + x;
            int yy = dy[k] + y;

            if(isValid(M, xx, yy, V)) {
                V[xx][yy] = true;
                cur.add(new Point(xx, yy));
                helper(M, xx, yy, pkgs, V,cur);
                cur.remove(cur.size() - 1);
                V[xx][yy] = false;
            }
        }
    }

    private boolean isValid(int[][] m, int x, int y, boolean[][] v) {
        return (x >= 0 && y >= 0 && x < m.length && y < m[0].length && m[x][y] != -1 && !v[x][y]);
    }

    public static void main(String args[]) {
        int[][] M = {{0, 0, -1, 0}, {0, 3, 0, 7}, {0, -1, 0, 8}};

        Set<Integer> pkgs = new HashSet<>();
        pkgs.add(3);
        pkgs.add(7);
        pkgs.add(8);

        List<List<Point>> result = new FindPathForPackages().findPath(M, pkgs);

        System.out.println(result);
    }
}