魔闆(最小步數)

題目:

#include <bits/stdc++.h>
using namespace std;
string st,en;
map<string,int> dis;
map<string,pair<char,string>> pre;
queue<string> q;
string move0(string a)
{
    string ans;
    for(int i=7;i>=0;i--) ans+=a[i];
    return ans;
}
string move1(string a)
{
    string ans;
    ans+=a[3];
    for(int i=0;i<=2;i++) ans+=a[i];
    for(int i=5;i<=7;i++) ans+=a[i];
    ans+=a[4];
    return ans;
}
string move2(string a)
{
    string ans;

    ans+=a[0];
    ans+=a[6];
    ans+=a[1];
    ans+=a[3];
    ans+=a[4];
    ans+=a[2];
    ans+=a[5];
    ans+=a[7];

    return ans;

}
void bfs()
{
    q.push(st);
    dis[st]=0;
    while(!q.empty())
    {
        string t=q.front();
        q.pop();
        string m[5];
        m[0]=move0(t);
        m[1]=move1(t);
        m[2]=move2(t);
        for(int i=0;i<=2;i++)
        {
            string s=m[i];
            if(dis.count(s)==0)
            {
                q.push(s);
                pre[s].first='A'+i;
                pre[s].second=t;
                dis[s]=dis[t]+1;
                if(s==en) break;
                q.push(s);
            }
        }
    }
}
int main()
{
    for(int i=0;i<8;i++)
    {
        int a;
        cin>>a;
        en+=a+'0';
    }
    st="12345678";
    bfs();
    string ans;
    cout<<dis[en]<<endl;
    while(st!=en)
    {
        ans+=pre[en].first;
        en=pre[en].second;
    }
    reverse(ans.begin(),ans.end());
    if(ans!="") cout<<ans<<endl;
    return 0;
}