自我想法

说实话，在Y老师用unordered_map时我是真的不明白，也许是我太弱了。于是我想有没有可以直接用map的方法

题目描述

这是一张有 8 个大小相同的格子的魔板：

1 2 3 4
8 7 6 5
我们知道魔板的每一个方格都有一种颜色。

这 8 种颜色用前 8 个正整数来表示。

可以用颜色的序列来表示一种魔板状态，规定从魔板的左上角开始，沿顺时针方向依次取出整数，构成一个颜色序列。

对于上图的魔板状态，我们用序列 (1,2,3,4,5,6,7,8) 来表示，这是基本状态。

这里提供三种基本操作，分别用大写字母 A，B，C 来表示（可以通过这些操作改变魔板的状态）：

A：交换上下两行；
B：将最右边的一列插入到最左边；
C：魔板中央对的4个数作顺时针旋转。


你要编程计算用最少的基本操作完成基本状态到特殊状态的转换，输出基本操作序列。

输入样例

2 6 8 4 5 7 3 1

输入样例

7
BCABCCB

分析

对于这道题，我们可以开两个map数组，一个记录状态，另一个记录前驱，而对应的每个操作，我们其实不用像
Y老师那样专业，数组模拟也能做到，最后得到答案后，在一个一个往回跳，判断每次对应的操作就行了，最后统一输出

代码

//#pragma GCC optimize(3,"inline","Ofast","fast-math","no-stack-protector","unroll-loops")
//#pragma GCC target("sse","sse2","sse3","sse4","avx","avx2","popcnt")

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<map>

#define RG register
#define ll long long
#define INF 0x3f3f3f3f

using namespace std;

const int N=9;

int tot;
char a[N*N];

map<string,string>pre;
map<string,int>dist;

queue<string>q;

inline string Get_1(string k)
{
    string res="";
    for (int i=7;i>=4;i--) res+=k[i];
    for (int i=3;i>=0;i--) res+=k[i];
    return res;
}//对行列变换 

inline string Get_3(string k)
{
    string res="";
    res+=k[0];
    res+=k[6];
    res+=k[1];
    res+=k[3];
    res+=k[4];
    res+=k[2];
    res+=k[5];
    res+=k[7];

    return res;
}//一个一个加 

inline string Get_2(string k)
{
    string res="";
    res+=k[3];
    for (int i=0;i<3;i++) res+=k[i];
    for (int i=5;i<8;i++) res+=k[i];
    res+=k[4];
    return res;
}

inline void BFS(string end)
{
    string v0="12345678";
    if(end==v0) return ;

    dist[v0]=0;
    q.push(v0);

    while(!q.empty())
    {
        string k=q.front();q.pop();
        string x[4];
        x[0]=Get_1(k);
        x[1]=Get_2(k);
        x[2]=Get_3(k);

        for (int i=0;i<3;i++)
        {
            string str=x[i];
            if(dist[str]==0)
            {
                dist[str]=dist[k]+1;
                pre[str]=k;
                if(str==end) break;
                q.push(str);
            }
        }
    }
}

inline void check(string end)
{
    string op=pre[end];
    if(op[0]==end[7]&&op[1]==end[6]&&op[2]==end[5]&&op[3]==end[4])
    {
        a[++tot]='A';
        return ;
    }
    else if(op[1]==end[2]&&op[2]==end[5]&&op[6]==end[1]&&op[5]==end[6])
    {
        a[++tot]='C';
        return ;
    }
    else a[++tot]='B';
}

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

    BFS(end);

    cout<<dist[end]<<"\n";

    string vo="12345678";
    while(end!=vo)
    {
        check(end);
        end=pre[end];
    }

    if(dist[end])
        for (int i=tot;i>=1;i--) cout<<a[i];

    return 0;
}