hanoi puzzle

hanoi puzzle.cpp

// Zhiqiang Ma (http://www.ericzma.com)
#include <iostream>
#include <iomanip>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>

#include <sys/time.h>

typedef std::vector<int> VI;
typedef std::vector<VI> VVI;
typedef std::pair<int, int> PII;

struct Stat {
    VVI vec;
    std::vector<PII> moves;
};

VI input_int_vec(int n) {
    VI v(n);
    for (int i = 0; i < n; i++) {
        std::cin >> v[i];
    }
    return v;
}

VVI disk_vec_to_peg_vec(VI disks, int k, int n) {
    VI v[k];
    VVI vv;
    for (int i = n - 1; i >= 0; i--) {
        v[disks[i] - 1].push_back(i);
    }
    for (int i = 0; i < k; i++) {
        vv.push_back(v[i]);
    }
    return vv;
}

int main() {
    // get input
    int n, k;
    std::cin >> n >> k;
    VVI init = disk_vec_to_peg_vec(input_int_vec(n), k, n);
    VVI target = disk_vec_to_peg_vec(input_int_vec(n), k, n);

    // using set significantly improve the performance
    std::set<VVI> processed_stat;

    std::queue<Stat> q;
    q.push({.vec = init, .moves = {}});
    std::vector<PII> porder(k);
    int cnt = 0;
    while (!q.empty()) {
        cnt ++;
        Stat &stat = q.front();
        VVI &v = stat.vec;
        processed_stat.insert(v);
        // build and sort the pegs by the top disks
        for (int i = 0; i < k; i++) {
            int disk = std::numeric_limits<int>::max();
            if (!v[i].empty()) {
                disk = v[i].back();
            }
            porder[i].first = disk;
            porder[i].second = i;
        }
        sort(porder.begin(), porder.end());
        // enqueue next moves
        for (int ii = k - 1; ii >= 0; ii--) {
            int i = porder[ii].second;
            if (v[i].empty()) continue;
            // for (int jj = k - 1; jj > ii; jj--) {
            for (int jj = ii + 1; jj < k; jj++) {
                int j = porder[jj].second;
                int iback = v[i].back();
                // temporarily change v
                v[i].pop_back();
                v[j].push_back(iback);
                if (processed_stat.find(v) == processed_stat.end()) {
                    Stat new_stat {.vec = v, .moves = stat.moves};
                    new_stat.moves.push_back(PII {i, j});
                    if (new_stat.vec == target) {
                        std::cout << new_stat.moves.size() << std::endl;
                        for (auto &p : new_stat.moves) 
                            std::cout << p.first + 1 << ' ' << p.second + 1 << std::endl;
                        // std::cout << cnt << " times." << std::endl;
                        return 0; // the 1st one is enough
                    }
                    // enqueue the new_stat
                    q.push(new_stat);
                }
                // change items back
                v[i].push_back(iback);
                v[j].pop_back();
            } // for jj
        } // for ii
        q.pop();
    }
    return 0;
}