最短路径找treasure

board3 中1代表钻石，给出起点和终点，问有没有一条不走回头路的路线，能从起点走到终点，并拿走所有的钻石，给出所有的最短路径。

board3 = [
    [  1,  0,  0, 0, 0 ],
    [  0, -1, -1, 0, 0 ],
    [  0, -1,  0, 1, 0 ],
    [ -1,  0,  0, 0, 0 ],
    [  0,  1, -1, 0, 0 ],
    [  0,  0,  0, 0, 0 ],
]


treasure(board3, (5, 0), (0, 4)) -> None

treasure(board3, (5, 2), (2, 0)) ->
  [(5, 2), (5, 1), (4, 1), (3, 1), (3, 2), (2, 2), (2, 3), (1, 3), (0, 3), (0, 2), (0, 1), (0, 0), (1, 0), (2, 0)]
  Or
  [(5, 2), (5, 1), (4, 1), (3, 1), (3, 2), (3, 3), (2, 3), (1, 3), (0, 3), (0, 2), (0, 1), (0, 0), (1, 0), (2, 0)]

treasure(board3, (0, 0), (4, 1)) ->
  [(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3), (2, 2), (3, 2), (3, 1), (4, 1)]
  Or
  [(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3), (3, 3), (3, 2), (3, 1), (4, 1)]

DFS 遍历所有路径，然后再找最短的

   public static List<int[]> findPath(int[][] matrix, int[] start, int[] end)
    {
        List<int[]> res = new ArrayList<>();
        int treasureCount = 0;
        for(int i = 0; i< matrix.length; i++)
        {
            for(int j = 0; j< matrix[0].length; j++)
            {
                if(matrix[i][j] == 1)
                {
                    treasureCount++;
                }
            }
        }

        List<int[]> path = new ArrayList<>();
        List<List<int[]>> allPossiblePaths = new ArrayList<>();
        dfs(matrix, start[0], start[1], end, treasureCount, path, allPossiblePaths);

        int shortestSize = Integer.MAX_VALUE;
        for(int i = 0; i< allPossiblePaths.size(); i++)
        {
            if(allPossiblePaths.get(i).size() < shortestSize)
            {
                shortestSize = allPossiblePaths.get(i).size();
                res = allPossiblePaths.get(i);
            }
        }
        return res;
    }

    public static void dfs(int[][] matrix, int x, int y, int[] end, int remainTreasure, List<int[]> path, List<List<int[]>> allPossiblePaths)
    {
        if(!isBound(matrix, x, y) || matrix[x][y] == -1 || matrix[x][y] == 2)
        {
            return;
        }

        path.add(new int[]{x,y});
        
        if(matrix[x][y] == 1)
        {
            remainTreasure--;
        }

        if(x == end[0] && y == end[1] && remainTreasure == 0)
        {
            allPossiblePaths.add(new ArrayList<>(path));
            path.remove(path.size()-1);
            //matrix[x][y] = temp;
            return;
        }

        // Mark as 2 for already visited
        int temp = matrix[x][y];
        matrix[x][y] = 2;
        dfs(matrix, x-1, y, end, remainTreasure, path, allPossiblePaths);
        dfs(matrix, x+1, y, end, remainTreasure, path, allPossiblePaths);
        dfs(matrix, x, y-1, end, remainTreasure, path, allPossiblePaths);
        dfs(matrix, x, y+1, end, remainTreasure, path, allPossiblePaths);
        matrix[x][y] = temp;
        path.remove(path.size()-1);
    }

    public static boolean isBound(int[][] matrix, int i, int j)
    {
        return i>=0 && i<matrix.length && j>=0 && j<matrix[0].length;
    }

3KB

ShortPathFindingTreasure.java

Open