enum ReindeerDirection { NORTH, SOUTH, EAST, WEST }

class MazeState {
    private int points;
    private final Point location;
    private final ReindeerDirection direction;

    public MazeState() { this.location = new Point(); this.direction = ReindeerDirection.EAST; this.points = 0; }
    public MazeState(Point location, ReindeerDirection direction, int points) {
        this.location = location;
        this.direction = direction;
        this.points = points;
    }

    public Point getLocation() { return location; }
    public ReindeerDirection getDirection() { return direction; }
    public int getPoints() { return points; }
    public void setPoints(int points) { this.points = points; }
    public String toString() { return this.location.toString(); }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        MazeState mazeState = (MazeState) o;
        return Objects.equals(location, mazeState.location) && direction == mazeState.direction;
    }

    @Override
    public int hashCode() {
        return Objects.hash(location, direction);
    }
}

class MazePointComparator implements Comparator<MazeState> {
    @Override
    public int compare(MazeState x, MazeState y) {
        return Integer.compare(x.getPoints(), y.getPoints());
    }
}

// Fairly confident the bug is not in here as this is the same neighbor-finding function I used in part 1.
private static List<MazeState> getNeighbors(char[][] grid, MazeState node) {
    List<MazeState> neighbors = new ArrayList<>();

    Point p = node.getLocation();
    ReindeerDirection direction = node.getDirection();
    int points = node.getPoints();

    if (direction == ReindeerDirection.NORTH) {
        if (grid[p.x-1][p.y] == '.') {
            neighbors.add(new MazeState(new Point(p.x-1, p.y), direction, points + 1));
        }
        if (grid[p.x][p.y-1] == '.') {
            neighbors.add(new MazeState(p, ReindeerDirection.WEST, points + 1000));
        }
        if (grid[p.x][p.y+1] == '.') {
            neighbors.add(new MazeState(p, ReindeerDirection.EAST, points + 1000));
        }
    } else if (direction == ReindeerDirection.EAST) {
        if (grid[p.x][p.y+1] == '.') {
            neighbors.add(new MazeState(new Point(p.x, p.y+1), direction, points + 1));
        }
        if (grid[p.x-1][p.y] == '.') {
            neighbors.add(new MazeState(p, ReindeerDirection.NORTH, points + 1000));
        }
        if (grid[p.x+1][p.y] == '.') {
            neighbors.add(new MazeState(p, ReindeerDirection.SOUTH, points + 1000));
        }
    } else if (direction == ReindeerDirection.SOUTH) {
        if (grid[p.x+1][p.y] == '.') {
            neighbors.add(new MazeState(new Point(p.x+1, p.y), direction, points + 1));
        }
        if (grid[p.x][p.y-1] == '.') {
            neighbors.add(new MazeState(new Point(p.x, p.y), ReindeerDirection.WEST, points + 1000));
        }
        if (grid[p.x][p.y+1] == '.') {
            neighbors.add(new MazeState(new Point(p.x, p.y), ReindeerDirection.EAST, points + 1000));
        }
    } else if (direction == ReindeerDirection.WEST) {
        if (grid[p.x][p.y-1] == '.') {
            neighbors.add(new MazeState(new Point(p.x, p.y-1), direction, points + 1));
        }
        if (grid[p.x-1][p.y] == '.') {
            neighbors.add(new MazeState(new Point(p.x, p.y), ReindeerDirection.NORTH, points + 1000));
        }
        if (grid[p.x+1][p.y] == '.') {
            neighbors.add(new MazeState(new Point(p.x, p.y), ReindeerDirection.SOUTH, points + 1000));
        }
    }

    return neighbors;
}


private static int part2(char[][] grid, Point start, Point end) {
    Map<MazeState, Integer> costs = new HashMap<>(); // maps the best known costs to reach a given maze state so far
    Set<MazeState> visited = new HashSet<>();
    PriorityQueue<MazeState> pq = new PriorityQueue<>(new MazePointComparator());
    // for each maze state key, tracks a list of parent maze states that could get us to that maze state.
    Map<MazeState, List<MazeState>> parents = new HashMap<>();

    MazeState initial = new MazeState(start, ReindeerDirection.EAST, 0);
    pq.add(initial);
    costs.put(initial, 0);

    while (!pq.isEmpty()) {
        MazeState node = pq.poll();
        Point p = node.getLocation();

        if (visited.contains(node)) continue;

        visited.add(node);

        List<MazeState> neighbors = getNeighbors(grid, node);

        // For each neighbor, if the distance of the source node to the current node (dist[current]) plus
        // the cost to get from current node to the neighbor (weight[current, neighbor])
        // is less than the best recorded cost of the source node to the neighbor (dist[neighbor]) already,
        // we update the cost to the neighbor to the new cost value.
        // In other words, we update if: dist[current] + cost[current, neighbor] < dist[neighbor]
        for (MazeState neighbor : neighbors) {
            if (!visited.contains(neighbor)) {
                // Check if our costs map contains these maze states. If not, initialize their costs to infinity.
                if (!costs.containsKey(node)) {
                    costs.put(node, Integer.MAX_VALUE);
                }
                if (!costs.containsKey(neighbor)) {
                    costs.put(neighbor, Integer.MAX_VALUE);
                }

                int newCost = costs.get(node) + neighbor.getPoints();

                // If we've found a better cost, update it.
                if (newCost <= costs.get(neighbor)) {
                    costs.put(neighbor, newCost);
                    pq.add(neighbor);

                    // And keep track of where we've come from
                    if (parents.containsKey(neighbor)) {
                        parents.get(neighbor).add(node);
                    } else {
                        List<MazeState> parentsOfNeighbor = new ArrayList<>();
                        parentsOfNeighbor.add(node);
                        parents.put(neighbor, parentsOfNeighbor);
                    }
                }
            }
        }
    }

    Set<Point> uniquePoints = new HashSet<>();

    // Find the min points.
    int min = Integer.MAX_VALUE;
    for (MazeState state : parents.keySet()) {
        if (state.getLocation().equals(end)) {
            min = Math.min(min, state.getPoints());
        }
    }

    // Find each end state that results in the minimum points in reaching it.
    List<MazeState> endStates = new ArrayList<>();
    for (MazeState state : parents.keySet()) {
        if (state.getLocation().equals(end) && state.getPoints() == min) {
            endStates.add(state);
        }
    }

    for (MazeState endState: endStates) {
        Stack<MazeState> stack = new Stack<>();
        stack.add(endState);

        // Work backwards from the end state, visiting the parent/previous states that got us to that state
        // and add their points to a set.
        while (!stack.isEmpty()) {
            MazeState curr = stack.pop();
            uniquePoints.add(curr.getLocation());

            if (parents.containsKey(curr)) {
                for (MazeState ms : parents.get(curr)) {
                    stack.push(ms);
                }
            }
        }
    }

    return uniquePoints.size();
}