来源

https://mp.weixin.qq.com/s/EF0vNHJKxKGz4E4OYmm7ig

题意：在一个3×3的网格中，1~8这8个数字和一个“x”恰好不重不漏地分布在这3×3的网格中。例如：

1 2 3
x 4 6
7 5 8
仅x位置可移动，且每次只能移动一格。给定初始状态和目标状态，要求移动若干步后变成给定的目标状态。有点类似玩鲁比克方块(魔方)。

解析：这一道题非常经典，但要在11分48秒内写完代码也比较难，需要理解透问题求解的每一个细节，灵活应用知识点，是学习搜索的必过之题。11分48秒内准确无误写完88行代码并AC，还是得有有几个小时训练才能做到。
知识点：二维坐标系及坐标系统转换
存储问题：用一维数组存储。
行数：i/ 3 （取商的整数），列：i % 3 (取余数)
挖掘点：（1）当逆序对为奇数时无解，也就是说不是所有的初始状态都能到达目标状态。（2）曼哈顿距离作为估价函数。横坐标差、纵坐标差、到达当前状态移动的最小步数三者总和最小可取得移动最少步。
算法基础：小根堆、搜索剪枝、最短路径问题。

int bfs(string start)
{
    int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
    priority_queue<pii,vector<pii>,greater<pii>> heap;
   unordered_map<string ,int >dist;
   unordered_map<string ,bool >st;

   dist[start]=0;
   heap.push({f(start),start});

   while(heap.size())
   {
       auto t=heap.top();heap.pop();

       string state=t.second;
       if(state=="12345678x") break;
       if(st[state])continue;
       st[state]=true;

       int x,y;
       fir(i,0,9)
       if(state[i]=='x')
       {
           x=i/3,y=i%3;
           break;
       }

       string raw=state;
       int step= dist[state];

       fir(i,0,4)
       {
           int a=x+dx[i],b=y+dy[i];
           if(a>=0 && a<3 && b>=0 && b<3)
           {
               state=raw;
               swap(state[a*3+b],state[x*3+y]);
               if(!dist.count(state) || dist[state]>step+1)
               {
                   dist[state]=step+1;
                   heap.push({f(state)+dist[state],state});

               }
           }
       }



   }
   string end="12345678x";
   if(dist[end]!=0) return dist[end];
   else 
    return -1;
}