Version1

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>

using namespace std;

class Cube
{
    enum {TOP = 0, FRONT, RIGHT, BOTTOM, BACK, LEFT};
    enum {_1 = 0, _2 = 1, _3 = 2, _4 = 3};

public:
    using Type = unsigned int;

    Cube() : data{ "WWWW", "RRRR", "YYYY", "BBBB", "OOOO", "GGGG" } {} //"WWWW", "RRRR", "BBBB", "YYYY", "OOOO", "GGGG"

    Cube(const vector<string> &input)
    {
        data = input;
    }

    Cube(const Cube &c) : data{ c.data }, repeat_cnt{ c.repeat_cnt }, path{ c.path } {}

    Cube(Cube &&c) : data{ move(c.data) }, repeat_cnt{ c.repeat_cnt }, path{ move(c.path) } {}

    const Cube& operator=(const Cube &c)
    {
        data = c.data;
        path = c.path;

        return *this;
    }

    const Cube& operator=(Cube &&c)
    {
        data = move(c.data);
        path = move(c.path);

        return *this;
    }

    friend ostream& operator<<(ostream &out, const Cube &c)
    {
        for (auto &x : c.data)
            out << x << endl;

        return out;
    }

    bool operator==(const Cube &c) const
    {
        static const vector<int> face{ TOP,FRONT,RIGHT,BOTTOM,BACK,LEFT };

        for (auto x : face)
            if (to_uint(x) != c.to_uint(x))
                return false;

        return true;
    }

    void flip(int i)
    {
        switch (i)
        {
        case 1:
            L();
            break;
        case 2:
            Lp();
            break;
        case 3:
            U();
            break;
        case 4:
            Up();
            break;
        case 5:
            B();
            break;
        case 6:
            Bp();
            break;
        default:
            cout << "flip error" << endl;
            break;
        }

        add_path(i);
    }

    Cube flip_cp(int i) const
    {
        Cube c{ *this };

        c.flip(i);

        return c;
    }

    Type hash(void) const
    {
        vector<Type> n{ to_uint(0) ,to_uint(1) ,to_uint(2) ,to_uint(3) ,to_uint(4) ,to_uint(5) };

        return n[0] * 17 + n[1] * 11 + n[2] * 3 - n[3] * 7 + n[4] * 13 - n[5] * 19;
    }

    void add_path(int i)
    {
        if (get_last_path() == i)
            ++repeat_cnt;
        else
            repeat_cnt = 1;

        path += ('0' + i);
    }

    int get_last_path(void) const
    {
        return path.empty() ? 0 : path[path.size() - 1] - '0';
    }

    int get_cnt(void) const
    {
        return repeat_cnt;
    }

    const string& get_path(void) const
    {
        return path;
    }

private:

    vector<string> data;
    int repeat_cnt;
    string path;


    Type to_uint(int idx) const
    {
        return *reinterpret_cast<const Type*>(data[idx].data());
    }

    void L(void)
    {
        auto tem = data[LEFT][_1];

        // left
        data[LEFT][_1] = data[LEFT][_3];
        data[LEFT][_3] = data[LEFT][_4];
        data[LEFT][_4] = data[LEFT][_2];
        data[LEFT][_2] = tem;

        // top
        tem = data[TOP][_1];
        auto tem2 = data[TOP][_3];

        data[TOP][_1] = data[BACK][_4];
        data[TOP][_3] = data[BACK][_2];

        // back
        data[BACK][_4] = data[BOTTOM][_1];
        data[BACK][_2] = data[BOTTOM][_3];

        // bottom
        data[BOTTOM][_1] = data[FRONT][_1];
        data[BOTTOM][_3] = data[FRONT][_3];

        // front
        data[FRONT][_1] = tem;
        data[FRONT][_3] = tem2;
    }

    void Lp(void)
    {
        auto tem = data[LEFT][_1];

        // left
        data[LEFT][_1] = data[LEFT][_2];
        data[LEFT][_2] = data[LEFT][_4];
        data[LEFT][_4] = data[LEFT][_3];
        data[LEFT][_3] = tem;

        // top
        tem = data[TOP][_1];
        auto tem2 = data[TOP][_3];

        data[TOP][_1] = data[FRONT][_1];
        data[TOP][_3] = data[FRONT][_3];

        // front
        data[FRONT][_1] = data[BOTTOM][_1];
        data[FRONT][_3] = data[BOTTOM][_3];

        // bottom
        data[BOTTOM][_1] = data[BACK][_4];
        data[BOTTOM][_3] = data[BACK][_2];

        // back
        data[BACK][_4] = tem;
        data[BACK][_2] = tem2;
    }

    void U(void)
    {
        auto tem = data[TOP][_1];

        // top
        data[TOP][_1] = data[TOP][_3];
        data[TOP][_3] = data[TOP][_4];
        data[TOP][_4] = data[TOP][_2];
        data[TOP][_2] = tem;

        // front
        tem = data[FRONT][_1];
        auto tem2 = data[FRONT][_2];

        data[FRONT][_1] = data[RIGHT][_1];
        data[FRONT][_2] = data[RIGHT][_2];

        // right
        data[RIGHT][_1] = data[BACK][_1];
        data[RIGHT][_2] = data[BACK][_2];

        // back
        data[BACK][_1] = data[LEFT][_1];
        data[BACK][_2] = data[LEFT][_2];

        // left
        data[LEFT][_1] = tem;
        data[LEFT][_2] = tem2;
    }

    void Up(void)
    {
        auto tem = data[TOP][_1];

        // top
        data[TOP][_1] = data[TOP][_2];
        data[TOP][_2] = data[TOP][_4];
        data[TOP][_4] = data[TOP][_3];
        data[TOP][_3] = tem;

        // front
        tem = data[FRONT][_1];
        auto tem2 = data[FRONT][_2];

        data[FRONT][_1] = data[LEFT][_1];
        data[FRONT][_2] = data[LEFT][_2];

        // left
        data[LEFT][_1] = data[BACK][_1];
        data[LEFT][_2] = data[BACK][_2];

        // back
        data[BACK][_1] = data[RIGHT][_1];
        data[BACK][_2] = data[RIGHT][_2];

        // right
        data[RIGHT][_1] = tem;
        data[RIGHT][_2] = tem2;

    }

    void B(void)
    {
        auto tem = data[BACK][_1];

        // back
        data[BACK][_1] = data[BACK][_3];
        data[BACK][_3] = data[BACK][_4];
        data[BACK][_4] = data[BACK][_2];
        data[BACK][_2] = tem;

        // top
        tem = data[TOP][_1];
        auto tem2 = data[TOP][_2];

        data[TOP][_1] = data[RIGHT][_2];
        data[TOP][_2] = data[RIGHT][_4];

        // right
        data[RIGHT][_2] = data[BOTTOM][_4];
        data[RIGHT][_4] = data[BOTTOM][_3];

        // bottom
        data[BOTTOM][_3] = data[LEFT][_1];
        data[BOTTOM][_4] = data[LEFT][_3];

        // LEFT
        data[LEFT][_1] = tem2;
        data[LEFT][_3] = tem;
    }

    void Bp(void)
    {
        auto tem = data[BACK][_1];

        // back
        data[BACK][_1] = data[BACK][_2];
        data[BACK][_2] = data[BACK][_4];
        data[BACK][_4] = data[BACK][_3];
        data[BACK][_3] = tem;

        // top
        tem = data[TOP][_1];
        auto tem2 = data[TOP][_2];

        data[TOP][_1] = data[LEFT][_3];
        data[TOP][_2] = data[LEFT][_1];

        // LEFT
        data[LEFT][_1] = data[BOTTOM][_3];
        data[LEFT][_3] = data[BOTTOM][_4];

        // bottom
        data[BOTTOM][_3] = data[RIGHT][_4];
        data[BOTTOM][_4] = data[RIGHT][_2];

        // right
        data[RIGHT][_2] = tem;
        data[RIGHT][_4] = tem2;
    }
};


class CubePermutation
{
public:
    CubePermutation() : data(15)
    {
        vector<int> reserve_s{ 1,10,40,200,600,2500,9000,33500,114500,361000,931000,1351000,783000,91000,300 };

        for (int i = 0; i < data.size(); ++i)
            data[i].reserve(reserve_s[i]);

        data[0].push_back(Cube{});

        mp.reserve(4000000);
    }

    void run()
    {
        permutate();

        int t = 0;

        for (int i = 0; i < data.size(); ++i)
        {

            cout << i << " size = " << data[i].size() << endl;

            t += data[i].size();
        }

        cout << "total = " << t << endl;

    }

    int find(const vector<string> &input) const
    {
        Cube c{ input };

        auto key = c.hash();

        auto range = mp.equal_range(key);

        for(auto itr = range.first;itr != mp.end() && itr != range.second;++itr)
            if (c == itr->second)
            {
                auto ans = itr->second.get_path();

                cout << "org setps : " << ans << endl;

                for(auto i = ans.begin();i!=ans.end();++i)
                    switch (*i)
                    {
                    case '1':
                    case '2':
                        *i = '2' - *i + '1';
                        break;
                    case '3':
                    case '4':
                        *i = '4' - *i + '3';
                        break;
                    case '5':
                    case '6':
                        *i = '6' - *i + '5';
                        break;
                    }

                char ch;
                for (int i = 0, k = ans.size() - 1; i < k; ++i, --k)
                {
                    ch = ans[i];
                    ans[i] = ans[k];
                    ans[k] = ch;
                }


                cout << "sol steps : " << ans << endl;
                return ans.size();
            }

        return -1;
    }

private:
    enum { L = 1, Lp, U, Up, B, Bp };

    vector<vector<Cube>> data;
    unordered_multimap<Cube::Type, Cube&> mp;

    void permutate(void)
    {
        int now, pre;
        int i, k;

        for (now = 1; now <= 14; ++now)
        {
            pre = now - 1;


            for (i = 0; i < data[pre].size(); ++i)
            {
                for (k = 1; k <= 6; ++k)
                {
                    if (is_redundant(pre, i, k))
                        continue;


                    data[now].emplace_back(data[pre][i].flip_cp(k));

                    check_exsited(now, data[now].size() - 1);
                }
            }
        }
    }

    bool is_redundant(int pre, int idx, int now_step ) const
    {
        int last_step = data[pre][idx].get_last_path();
        int m, M;

        if (now_step == last_step && ((last_step == Lp) || (last_step == Up) || (last_step == Bp)))
            return true;

        if (now_step == last_step && data[pre][idx].get_cnt() == 2)
            return true;

        if (last_step < now_step)
        {
            m = last_step;
            M = now_step;
        }
        else
        {
            m = now_step;
            M = last_step;
        }

        if (M - m == 1 && (m & 0x01))
            return true;

        return false;
    }

    void check_exsited(int now, int idx)
    {
        auto key = data[now][idx].hash();

        auto range = mp.equal_range(key);
        bool found = false;

        if (range.first != mp.end())
            for (auto itr = range.first; itr != range.second; ++itr)
                if (itr->second == data[now][idx])
                    found = true;

        if (found)
            data[now].pop_back();
        else
            mp.emplace(key, data[now][idx]);
    }
};


int main(void)
{
    CubePermutation p;

    p.run();


    vector<string> input(6);

    while (true)
    {
        cout << "input:" << endl;

        for (int i = 0; i < 6; ++i)
            getline(cin, input[i]);

        auto step = p.find(input);

        cout << "total " << step << endl;
    }


    cin.get();
    return 0;
}