适合初学者看通俗易懂C++

解题思路:    

        1.题目要求最小步数，利用BFS搜索，一旦找到就是最小步数；

        2.使用双向搜索减少时间，分别从初态和终态使用BFS，使用map关联数组命名为maps的键记录变化过程中每一种字符串状态，其中，从初态开始变化的键对应的值都计为1，从终态开始变化的键对应的值都计为2

        3.当从初态和终态变化得到的状态一样时，代表可以从初态变化到终态，获得最小步数；若从初态和从终态得到的所有状态都没有一样的时，代表无论多少步都不可到达，输出结果-1

        4.利用map关联数组命名为steps记录从出态和终态移动了多少步数，当从初态和终态移动得到一样状态时，即maps的值相加等于3时，将从出态移动的步数和从终态移动的步数相加得到结果。

        5.这里用字符串表示表格状态，对于如何找到“.”以及如何让空白与数字交换，利用如下方法：

                以题目初态为例，将12345678.赋值给string initial，那么得到字符串的中字符位置用i*3+j表示

int t;
int x, y;
for(int i = 0; i<3; i++){
    for(int j = 0; j<3; j++){
	t = i*3+j;     
	if(initial[t] == '.'){
	    x = i;
	    y = j;
	    break;
			}
	}
}
t = x*3+y;

            设置横纵坐标x,y，若表格中数字想向上移动一个位置，即列不变，行减一，那么移动后finalx=x-1;finaly=y;数字想向左移动一个位置，即行不变，列减一，那么移动后finalx=x;finaly=y-1;找到finalx,finaly后，将变化前initial字符串中finalx*3+finaly位置对应的值赋给变化后final字符串x*3+y位置，后者同理，这样就完成了数字在表格中的移动，并且获得了从初态到下一状态的变化，注意final代表的是变化后的状态，initial代表的是变化前的状态，不应当是初态，也可以是终态，或者变化过程中任一状态;

注意fianlx,finay均要满足>=0且<3                                                 

string final = initial;
	final[t] = initial[finalx*3+finaly];
	final[nx*3+ny] = initial[t];

        6.步数共有三种情况:(1)输入时初态和终态就相同，步数直接输出0；

                                       (2)初态终态初始时不相同，但是可以通过转化得到，计算步数输出;

                                       (3)初态和终态初始时不同，但是无法通过转换得到，输出-1

知识了解：

1. queue:只能访问 queue<T> 容器适配器的第一个和最后一个元素。只能在容器的末尾添加新元素，只能从头部移除元素。

   front()：返回 queue 中第一个元素的引用。如果 queue 是常量，就返回一个常引用；如果 queue 为空，返回值是未定义的。

   push(T&& obj)：以移动的方式在 queue 的尾部添加元素。这是通过调用底层容器的具有右值引用参数的成员函数 push_back() 来完成的。

   pop()：删除 queue 中的第一个元素。

   empty()：如果 queue 中没有元素的话，返回 true。

2.map<string, int> T 是一个声明，用于生成关联数组，该关联数组管理以string为键的int元素。初始int默认为0;

参考代码:

#include<iostream>
#include<map>
#include<queue>
#include<string>
using namespace std;
// 定义要用到的变量
// 位移
int yd[4][2]={1,0,-1,0,0,1,0,-1};
// 表格状态，由初态还是终态转变来
map<string,int> maps;
// 当前状态是第几步
map<string,int> steps;
// 输入字符串
string a,b;
// 双向bfs
int bfs(){
    // 若输入a,b相等,步数为零
    if(a==b){
        return 0;
    }
    queue<string> que;
    que.push(a);
    que.push(b);
    // 可以通过转化得到，计算步数
    while(!que.empty()){
        // 获取一个状态之后弹出它，若一直找不到相同状态就会把pue删除空，跳出循环
        string initial=que.front();
        que.pop();
        
        // 创建状态索引
        int t;
        // 创建坐标
        int x,y;
        // 找到空白，即“.”
        for(int i=0;i<3;i++){
            for(int j=0;j<3;j++){
                t=i*3+j;
                if(initial[t]=='.'){
                    x=i;
                    y=j;
                    break;
                }
            }
        }
        t=x*3+y;
        // 实现四种空白的位移，注意找到后的坐标要满足大于等于0且小于3才可进行空白的移动
        for(int i=0;i<4;i++){
            // 变换后x坐标
            int finalx=x+yd[i][0];
            int finaly=y+yd[i][1];
            // 转换后坐标是否满足条件,否则会超出表格
            if(finalx>=0&&finalx<3&&finaly>=0&&finaly<3){
                string final=initial;
                // 实现空白和目标位置交换，得到转化后状态
                final[t]=initial[finalx*3+finaly];
                final[finalx*3+finaly]=initial[t];
                // 如果maps里面这个键的值为0，代表这个状态第一次出现
                if(!maps[final]){
                    // 将转化前状态的maps值给现在状态的，表示现在状态由初态还是终态方向转化来的
                    maps[final]=maps[initial];
                    // 代表现在是该方向转化的第几步
                    steps[final]=steps[initial]+1;
                    /* 将该方向目前状态放入que，que循环里初态方向和终态方向交替循环,
                    每次进入都是该方向最新状态*/
                    que.push(final);
                }
                /* 如果交换后获得的状态已经存在，那么该状态已经改过键值，若与当前转换前状态键值
                相加为3，则代表来两个状态来自方向不一样但可以找到相同状态，即可找到最小步数。
                */
                else if(maps[final]+maps[initial]==3){
                    // 另一方向步数+当前方向转换前状态步数+现在这一步
                    return steps[final]+steps[initial]+1;
                }
                
                
            }
        }
    }
    return -1;
}
int main()
{
    cin>>a>>b;
    // 由初态a转化来的maps值为1，由终态b转化来的maps值为2
    maps[a]=1;
    maps[b]=2;
    cout<<bfs()<<endl;
    return 0;
}