题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<queue>
#include<unordered_map>
#include<string>
#include<algorithm>

using namespace std;

int g[2][4];
unordered_map<string, int> dist;
unordered_map<string, pair<char, string>> pre;

void set(string str)
{
    for (int i = 0; i < 4; i ++) g[0][i] = str[i];
    for (int i = 3; i >= 0; i --) g[1][i] = str[7 - i];
}

string  get()
{
    string res;
    for (int i = 0; i < 4; i ++) res += g[0][i];
    for (int i = 3; i >= 0; i --) res += g[1][i];
    return res;
}

string getA(string str)
{
    set(str);
    for (int i = 0; i < 4; i ++) swap(g[0][i], g[1][i]);
    return get();
}

string getB(string str)
{
    set(str);
    for(int i = 0; i < 2; i ++) swap(g[i][0], g[i][3]);
    for (int i = 3; i > 1; i --) 
        for (int j = 0; j < 2; j ++)
            swap(g[j][i], g[j][i - 1]);

    return get();
}

string getC(string str)
{
    set(str);
    char c = g[0][1];
    g[0][1] = g[1][1];
    g[1][1] = g[1][2];
    g[1][2] = g[0][2];
    g[0][2] = c;
    return get();
}

void bfs(string start, string end)
{
    queue<string> q;
    q.push(start);
    dist[start] = 0;

    while(q.size())
    {
        auto t = q.front();
        q.pop();

        string m[3];
        m[0] = getA(t);
        m[1] = getB(t);
        m[2] = getC(t);

        for (int i = 0; i < 3; i ++)
        {
            string str = m[i];
            //cout << str << " ";
            if (dist.count(str)) continue;

            dist[str] = dist[t] + 1;
            q.push(str);
            pre[str] = {'A' + i, t};
        }
        //cout << endl;

    }
}

int main()
{
    string start, end;
    for (int i = 0; i < 8; i ++) start += i + '1';
    for (int i = 0; i < 8; i ++)
    {
        int x;
        cin >> x;
        end += x + '0';
    }

    bfs(start, end);

    cout << dist[end] << endl;

    string res;
    while(end != start)
    {
        res += pre[end].first;
        end = pre[end].second;
    }
    reverse(res.begin(), res.end());
    if (res.size()) cout << res;
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla