不同路径 III

/*
 * 思路：
 * 使用Java Stream编写递归搜索方法来实现相同的逻辑。
 * 1. 找到起始位置和空格数量。
 * 2. 使用递归和流来处理搜索和回溯。
 */

import java.util.stream.Stream;

public class UniquePathsIIIStream {
    public int uniquePathsIII(int[][] grid) {
        int empty = 0, sx = -1, sy = -1;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 0) {
                    empty++;
                } else if (grid[i][j] == 1) {
                    sx = i;
                    sy = j;
                }
            }
        }
        return dfs(grid, sx, sy, empty);
    }

    private int dfs(int[][] grid, int x, int y, int empty) {
        if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == -1) {
            return 0;
        }
        if (grid[x][y] == 2) {
            return empty == -1 ? 1 : 0;
        }
        grid[x][y] = -1;
        empty--;
        int[] directions = {-1, 0, 1, 0, -1};
        int paths = Stream.of(1, 2, 3, 4)
                .mapToInt(i -> dfs(grid, x + directions[i], y + directions[i - 1], empty))
                .sum();
        grid[x][y] = 0;
        empty++;
        return paths;
    }
}