River Crossing

import java.util.*;

/**
 * @author thucdx
 */
class MonkAndDevil {
    static class MonkAndDevilSolver {
        int numberOfEach;
        int maxOnBoat;
        static int INF = (int) 1e9;

        public MonkAndDevilSolver(int numberOfEach, int maxOnBoat) {
            this.numberOfEach = numberOfEach;
            this.maxOnBoat = maxOnBoat;
        }

        Map<GameState, GameState> prev = new HashMap<>();
        Map<GameState, Integer> shortest = new HashMap<>();

        public List<GameState> solve() {
            List<GameState> steps = new ArrayList<>();
            // State at left side: n monks, n evil, boat is currently at this side
            Step first = new Step(numberOfEach, numberOfEach, true, 0);

            // Need to find the shortest path to Pair(0 - 0 monks, 0 - 0 devils, false - boat is at other side);
            Queue<Step> queue = new LinkedList<>();
            shortest.put(first.state, first.step);
            queue.add(first);

            while (!queue.isEmpty()) {
                Step cur = queue.poll();
                if (cur.getMonk() == 0 && cur.getDevil() == 0 && !cur.hasBoat()) {
                    // Trace back list of state
                    GameState curState = cur.state;
                    do {
                        steps.add(curState);
                        curState = prev.get(curState);
                    } while (prev.containsKey(curState));
                    steps.add(curState);

                    // Need to reverse
                    Collections.reverse(steps);
                    return steps;
                }

                List<GameState> gameStates = moveFrom(cur.state);
                for (GameState nextState : gameStates) {
                    if (shortest.getOrDefault(nextState, INF) > cur.step + 1) {
                        shortest.put(nextState, cur.step + 1);
                        Step nextStep = new Step(nextState, cur.step + 1);
                        queue.add(nextStep);
                        prev.put(nextStep.state, cur.state);
                    }
                }
            }

            return steps;
        }

        static void print(List<GameState> states) {
            for (int i = 1; i < states.size(); i++) {
                GameState last = states.get(i - 1);
                int monk = Math.abs(states.get(i).monk - states.get(i - 1).monk);
                int devil = Math.abs(states.get(i).devil - states.get(i - 1).devil);
                String s = String.format("Move %d monk(s) and %d devil(s) from %s",
                        monk, devil, last.hasBoat ? "left to right" : "right to left");
                System.out.println(s);
            }
        }

        List<GameState> moveFrom(GameState current) {
            List<GameState> possibleState = new ArrayList<>();
            if (current.hasBoat) {
                for (int devil = 0; devil <= maxOnBoat; devil++) {
                    for (int monk = 0; monk <= maxOnBoat - devil; monk++) {
                        if (devil == 0 && monk == 0) continue;

                        if (monk != 0 && monk < devil)
                            continue;

                        int monkLeft = current.monk - monk;
                        int devilLeft = current.devil - devil;

                        if (monkLeft < 0 || devilLeft < 0)
                            continue;

                        if (monkLeft > 0 && monkLeft < devilLeft)
                            continue;

                        int monkOtherSide = (numberOfEach - current.monk) + monk;
                        int devilOtherSide = (numberOfEach - current.devil) + devil;

                        if (monkOtherSide > 0 && monkOtherSide < devilOtherSide) {
                            continue;
                        }

                        if (monkOtherSide > numberOfEach || devilLeft > numberOfEach) {
                            continue;
                        }

                        possibleState.add(new GameState(monkLeft, devilLeft, false));
                    }
                }
            } else {
                List<GameState> states = moveFrom(new GameState(numberOfEach - current.monk, numberOfEach - current.devil, true));
                for (GameState state : states) {
                    possibleState.add(new GameState(numberOfEach - state.monk, numberOfEach - state.devil, true));
                }
            }
            return possibleState;
        }
    }


    static class Step implements Comparable<Step> {
        GameState state;
        int step;

        public Step(int first, int second, boolean hasBoat) {
            state = new GameState(first, second, hasBoat);
            step = 0;
        }

        public int getStep() {
            return step;
        }

        public int getMonk() {
            return state.monk;
        }

        public int getDevil() {
            return state.devil;
        }

        public boolean hasBoat() {
            return state.hasBoat;
        }
        public void setStep(int step) {
            this.step = step;
        }

        public Step(GameState other, int step) {
            this.state = other;
            this.step = step;
        }

        public Step(int first, int second, boolean hasBoat, int step) {
            state = new GameState(first, second, hasBoat);
            this.step = step;
        }

        @Override
        public String toString() {
            return "Step{" +
                    "step=" + step +
                    ", monk=" + state.monk +
                    ", devil=" + state.devil +
                    ", hasBoat=" + state.hasBoat +
                    '}';
        }

        @Override
        public int compareTo(Step o) {
            return step - o.step;
        }
    }

    static class GameState {
        int monk; // store number of monks
        int devil; // store number of devils
        boolean hasBoat;

        public GameState(int monk, int devil, boolean hasBoat) {
            this.monk = monk;
            this.devil = devil;
            this.hasBoat = hasBoat;
        }

        public GameState(GameState other) {
            this.monk = other.monk;
            this.devil = other.devil;
            this.hasBoat = other.hasBoat;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof GameState)) return false;

            GameState gameState = (GameState) o;

            if (monk != gameState.monk) return false;
            if (devil != gameState.devil) return false;
            return hasBoat == gameState.hasBoat;
        }

        @Override
        public int hashCode() {
            int result = monk;
            result = 31 * result + devil;
            result = 31 * result + (hasBoat ? 1 : 0);
            return result;
        }

        @Override
        public String toString() {
            return "Pair{" +
                    "monk=" + monk +
                    ", devil=" + devil +
                    ", hasBoat=" + hasBoat +
                    '}';
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        MonkAndDevilSolver solver = new MonkAndDevilSolver(n, m);
        List<GameState> states = solver.solve();
        if (states.size() == 0) {
            System.out.println("Cannot move!!!");
        } else {
            System.out.println("Finish in " + states.size() + " steps");
            MonkAndDevilSolver.print(states);
        }
    }
}