题解 | #八数码#

#include<bits/stdc++.h>
using namespace std;
const int N=363000;

string st[N];
unordered_map<string,int > mp;
int last[N];
bool used[N];//表示每一个状态是否使用过
int cnt=1;
string s,t="12345678x";
int dx[5]={0,1,-1,0,0},dy[5]={0,0,0,1,-1};//下上右左
char dic[10]={'0','d','u','r','l'};
char mv[N];
queue<int> q;

bool bfs(string s,string t)
{
    //初始s代表状态1
    mp[s]=1;
    st[1]=s;
    used[1]=1;
    q.push(1);
    last[1]=1;//不能有(如果选择dfs输出)

    while(!q.empty())
    {
        int tmp= q.front();//当前状态字符串对应的数字
        q.pop();
        string now_st=st[tmp];//当前状态字符串
        //cout<<"now_st="<<now_st<<endl;
        if(now_st==t)//最终状态
            {return true;break;}
        int k=now_st.find('x');
        int pos_x=k/3,pos_y=k%3;
        for(int i=1;i<=4;i++)//4个位置移动
        {
            int a=pos_x+dx[i],b=pos_y+dy[i];
            //移动后的状态字符串
            if(a>=0&&b>=0&&a<=2&&b<=2)
            {
                int move_x_pos=a*3+b;
                string nx=now_st;
                //cout<<k<<" "<<move_x_pos<<endl;
                swap(nx[k],nx[move_x_pos]);


                if(mp.find(nx)==mp.end())//表示第一次到达这个状态
                    {
                        mp[nx]=++cnt;
                        st[cnt]=nx;
                        
                        used[cnt]=1;
                        
                        last[cnt]=tmp;
                        mv[cnt]=dic[i];
                        
                        if(nx==t) {return true;break;}
                        q.push(cnt);//第二个状态

                }
                //swap(now_st[k],now_st[move_x_pos]);
            }
        }
    }
    return false;
}
void dfs(int t)
{
    if(last[t]!=0)
        {
            dfs(last[t]);
            cout<<mv[t];
        }
}
int main()
{
    stack<char> sc;
    char c;
    for(int i=0;i<9;i++)
    {
        cin>>c;
        s+=c;
    }
    if(!bfs(s,t))
        cout<<"unsolvable";
    else
    {
        //cout<<mp[t];
//         dfs(mp[t]);
        
        for(int i=cnt;i!=1;i=last[i])
        {
            sc.push(mv[i]);
        }
        while(!sc.empty())
        {
            cout<<sc.top();
            sc.pop();
        }
    }
    return 0;
}