游乐园的迷宫

/*
题目思路：
1. 使用 Java Stream API 遍历 points 确定每次转向方向。
2. 使用 direction 字符串的每个字符确定下一个点。
3. 输出一个满足条件的路径。
*/
import java.util.*;
import java.util.stream.IntStream;

public class SalesmanPathStream {
    public List<Integer> findPath(int[][] points, String direction) {
        List<Integer> path = new ArrayList<>();
        path.add(0); // 从第一个点开始
        Set<Integer> visited = new HashSet<>();
        visited.add(0);
        int prev = 0;

        direction.chars().forEach(d -> {
            OptionalInt nextPoint = IntStream.range(1, points.length)
                    .filter(i -> !visited.contains(i))
                    .filter(i -> isValidTurn(points, prev, path.get(path.size() - 1), i, (char) d))
                    .findFirst();
            nextPoint.ifPresent(i -> {
                path.add(i);
                visited.add(i);
                prev = path.get(path.size() - 2);
            });
        });

        path.add(path.get(0)); // 回到起点
        return path;
    }

    private boolean isValidTurn(int[][] points, int prev, int current, int next, char direction) {
        int[] v1 = {points[current][0] - points[prev][0], points[current][1] - points[prev][1]};
        int[] v2 = {points[next][0] - points[current][0], points[next][1] - points[current][1]};
        int crossProduct = v1[0] * v2[1] - v1[1] * v2[0];
        return (direction == 'L' && crossProduct > 0) || (direction == 'R' && crossProduct < 0);
    }

    public static void main(String[] args) {
        SalesmanPathStream sp = new SalesmanPathStream();
        int[][] points = {{1, 3}, {2, 4}, {3, 3}, {2, 1}};
        String direction = "LR";
        System.out.println(sp.findPath(points, direction));
    }
}