题目描述

详见8数码

注意点

unordered_map(哈希字典)比map(红黑树字典)更快，但红黑树字典也有自己的优点——有序，即map的元素都是按着“键”升序排列的。

/*
    Description:
    Date:
*/

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

using namespace std;

string end1="12345678x",start;
int dxy[4][2]={{0,1},{0,-1},{1,0},{-1,0}},seat,x,y,x_,y_,seat_,distance1;
char cun;

queue<string> q; 
unordered_map<string,int> mp; //这个unordered_map比map更快


int bfs1(){
    if(start==end1) return 0;
    mp[start]=1;//记录步长 
    while(1){

        seat=start.find('x');
        x=seat/3;y=seat%3;
        for(int i=0;i<4;i++)
        {

            x_=x+dxy[i][0]; y_=y+dxy[i][1];
            if(x_>=0 && x_<3 && y_>=0 && y_<3)
            {
                seat_=x_*3+y_;

                distance1=mp[start];

                swap(start[seat],start[seat_]);

                if(mp[start]==0)//首次到达状态a
                {

                    if(start==end1) return distance1;//如果到达终点，则结束 
                    mp[start]=distance1+1; 
                    q.push(start);//否则状态a入栈 
                }

                swap(start[seat],start[seat_]);
            }
        }
        //如果栈为空了还没找到，就说明没有结果了
        if(q.empty()) return -1;

        //出栈
        start=q.front();
        q.pop();
    }


}




int main()
{
    //cin>>start;

    for(int i=0;i<=8;i++)
    {
        cin>>cun;
        start+=cun;
    }
    cout<<bfs1(); 
    return 0;
}