题解 | #汉诺塔问题#

#include <unordered_map>
#include <vector>
#include <string>
class Solution {
    vector<string> strs;
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return string字符串vector
     */
    vector<string> getSolution(int n) {
        // write code here
        strs.resize(0);
	  	// 0b100 : left
	  	// 0b010 : mid
	  	// 0b001 : right
        move(n, 0b100, 0b001);
        return strs;
    }

    void move(int n, int from, int to) {
        if(n == 1) {
            move(from, to);
        } else {
		  	// 算出中继位置
            int mid = 0b111 & ~(from | to);
		  	// 将上方n-1个盘子搬往中继位置
            move(n - 1, from, mid);
		  	// 将最底下的盘子搬往目标位置
            move(from, to);
		  	// 将中继位置的n-1个盘子搬往目标位置
            move(n - 1, mid, to);
        }
    }

    void move(int from, int to) {
        static unordered_map<int, string> itos{
            {0b100, string("left")},
            {0b010, string("mid")},
            {0b001, string("right")}
        };
        strs.push_back("move from " + itos[from] + " to " + itos[to]);
    }
};