bfs,70分求助
查看原帖
bfs,70分求助
784813
SakurajiamaMai楼主2023/5/18 19:31
#include<bits/stdc++.h>
using namespace std;
char op[]="ABCD";
string ed;
unordered_map<string,char>d;
unordered_map<string,string>pre;
string swap0(string s)
{
    swap(s[0],s[2]),swap(s[0],s[8]),swap(s[0],s[6]);
    swap(s[1],s[3]),swap(s[3],s[5]),swap(s[3],s[7]);
    return s;
}
string swap1(string s)
{
    swap(s[0],s[2]),swap(s[2],s[8]),swap(s[8],s[6]);
    swap(s[1],s[3]),swap(s[1],s[7]),swap(s[1],s[5]);
    return s;
}
string swap2(string s)
{
    swap(s[0],s[2]),swap(s[3],s[5]),swap(s[6],s[8]);
    return s;
}
string swap3(string s)
{
    swap(s[0],s[6]),swap(s[1],s[7]),swap(s[2],s[8]);
    return s;
}
bool bfs(string st)
{
    priority_queue<string>que;
    que.push(st);
    d[st]=0;
    while(!que.empty())
    {
        string now=que.top();
        que.pop();
        if(now==ed) return true;
        string cop[4];
        cop[0]=swap0(now),cop[1]=swap1(now),cop[2]=swap2(now),cop[3]=swap3(now);
        for(int i=0;i<4;i++)
        {
            string tmp=cop[i];
            if(!d.count(tmp))
            {
                pre[tmp]=now;
                d[tmp]=i;
                que.push(tmp);
            }
        }
    }
    return false;
}
int main()
{
    string st;
    for(int i=0;i<9;i++)
    {
        char c;
        cin>>c;
        st+=c;
    }
    for(int i=0;i<9;i++)
    {
        char c;
        cin>>c;
        ed+=c;
    }
    if(ed==st)
    {
        cout<<"AB";
        return 0;
    }
    if(bfs(st))
    {
        string res,t=ed;
        while(t!=st)
        {
            res=res+op[d[t]];
            t=pre[t];
        }
        cout<<res<<endl;
    }
    else cout<<"Poland cannot into space!!!"<<endl;
    return 0;
}
2023/5/18 19:31
加载中...