题解 | #用栈来求解汉诺塔问题#

import java.util.LinkedList;
import java.util.Scanner;

/**
 * @author SongShengLin
 * @date 2022/1/9 11:16 PM
 * @description
 */
public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        scanner.close();
        int steps = hanoiProblem(num, "left", "mid", "right");
        System.out.println("It will move " + steps + " steps.");
    }

    public static int hanoiProblem(int num, String left, String mid, String right) {
        if (num < 1) {
            return 0;
        }
        LinkedList<Integer> lS = new LinkedList<>();
        LinkedList<Integer> mS = new LinkedList<>();
        LinkedList<Integer> rS = new LinkedList<>();
        lS.push(Integer.MAX_VALUE);
        mS.push(Integer.MAX_VALUE);
        rS.push(Integer.MAX_VALUE);
        for (int i = num; i > 0; i--) {
            lS.push(i);
        }
        Action[] record = {Action.No};
        int steps = 0;
        while (rS.size() != num + 1) {
            steps += fStackToStack(record, Action.MToL, Action.LToM, lS, mS, left, mid);
            steps += fStackToStack(record, Action.LToM, Action.MToL, mS, lS, mid, left);
            steps += fStackToStack(record, Action.RToM, Action.MToR, mS, rS, mid, right);
            steps += fStackToStack(record, Action.MToR, Action.RToM, rS, mS, right, mid);
        }
        return steps;
    }

    private static int fStackToStack(Action[] record, Action preNoAct, Action nowAct
            , LinkedList<Integer> fStack, LinkedList<Integer> tStack
            , String from, String to) {
        if (record[0] != preNoAct && fStack.peek() < tStack.peek()) {
            tStack.push(fStack.pop());

            System.out.println("Move " + tStack.peek() + " from " + from + " to " + to);
            record[0] = nowAct;
            return 1;
        }
        return 0;
    }

}


enum Action {
    /**
     * 行为枚举
     */
    No, LToM, MToL, MToR, RToM
}