179. 八数码

给定 n 个正整数，将它们分组，使得每组中任意两个数互质。

至少要分成多少个组？

在一个 3×3 的网格中，1∼8这 8 个数字和一个 X 恰好不重不漏地分布在这 3×3的网格中。

例如：

1 2 3
X 4 6
7 5 8

在游戏过程中，可以把 X 与其上、下、左、右四个方向之一的数字交换（如果存在）。

我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：

1 2 3
4 5 6
7 8 X

例如，示例中图形就可以通过让 X 先后与右、下、右三个方向的数字交换成功得到正确排列。

交换过程如下：

1 2 3   1 2 3   1 2 3   1 2 3
X 4 6   4 X 6   4 5 6   4 5 6
7 5 8   7 5 8   7 X 8   7 8 X

把 X 与上下左右方向数字交换的行动记录为 u、d、l、r。

现在，给你一个初始网格，请你通过最少的移动次数，得到正确排列。

输入格式

输入占一行，将 3×3的初始网格描绘出来。

例如，如果初始网格如下所示：

1 2 3 
x 4 6 
7 5 8 

则输入为：1 2 3 x 4 6 7 5 8

输出格式

输出占一行，包含一个字符串，表示得到正确排列的完整行动记录。

如果答案不唯一，输出任意一种合法方案即可。

如果不存在解决方案，则输出 unsolvable。

输入样例：

2  3  4  1  5  x  7  6  8 

输出样例

ullddrurdllurdruldr

解析 :   题目求的是路径操作，对于通常的bfs,如果没有搜到合法方案的话，bfs就要把所有的状态都要遍历一遍 9^9=387420489，即使能搜到合法状态,但是由于是一层一层搜，搜索量依旧很大，这题时间卡掉了这种做法。有没有好的搜索方法，A*算法就能很好的解决这种情况，它能把搜索范围迅速缩小。只要搜很小的一部分就能得到最优解。下面是A*算法的伪代码。

A*有点类似Dijkstra，它有两个 参数一个是 d[i]  表示从起点到当前点的距离 , 另外一个是 f[i] 表示当前点到终点的估价距离 <= 真实距离g[i]。

A*
while(!heap.empty())
{
    t <- 优先队列的队头
    当终点第一次出队的时候 break;
    
    for t 所有的邻边
        邻边入队
}
d[u]+f[u]<=d[u]+g[u]
如何保证第一次出队的终点就是最优解
证明: 假设u为最优路径上的一个点，至少起点是，假设终点出队时不是最优解,那么 dist > 最优解d >= d[u]+f[u];
如果不是最优解，那么队列中应该存在 一个点u使得 d[u]+f[u]<= 最优解d,此时就违反优先队列的规则了，最小的元素应该先出队，而现在却找到了比队头更小的元素，因此矛盾了。
//上面这个y总在提高课里讲的证明，但我感觉有问题，不是很懂的亚子。 #include<cstring>

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

#define x first
#define y second

using namespace std;

typedef pair<int,string> PIS;

const int N=9;

int f(string state)  //估价函数 算的是曼哈顿距离，即x,y 分别差值的绝对值之和
{
    int res=0;
    for(int i=0;i<state.size();++i)
    {
        if(state[i]!='x')
        {
            int t=state[i]-'1';
            res+=abs(t/3-i/3)+abs(t%3-i%3);
        }
    }
    return res;
}

string astar(string start)
{
    unordered_map<string,int> dist;
    unordered_map<string, pair<string,char>> prev; //保存前一个状态，和操作
    priority_queue<PIS,vector<PIS>,greater<PIS>>heap; //堆
    
    heap.push({f(start),start}); 
    string end={"12345678x"};  
    char op[4]={'u','d','l','r'};
    int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
    
    while(heap.size()) 
    {
        auto t=heap.top();
        heap.pop();
        
        string state=t.y;
        if(state==end) break;
        
        int x,y;
        for(int i=0; i<state.size(); ++i)
        {
          if(state[i]=='x') 
          {
               x=i/3,y=i%3;
               break;
          }
        }
        
        string source=state;
        for(int i=0;i<4;++i)
        {
            int a=x+dx[i],b=y+dy[i];
            if(a<0 || a>=3 || b<0 || b>=3) continue;
            
            swap(state[a*3+b],state[3*x+y]);
            
            if(!dist.count(state) || dist[state]>dist[source]+1)
            {
                dist[state]=dist[source]+1;
                prev[state]={source,op[i]};
                heap.push({dist[state]+f(state),state});
            }
           swap(state[a*3+b],state[3*x+y]);
        }
          
    }
    
    string res;
    while(end!=start)
    {
        res+=prev[end].y;
        end=prev[end].x;
    }
    reverse(res.begin(),res.end());  //取反，原因res加入的时候,是倒着加入的所以，最终的结果是反着来的，也就是从终点到起点，而我们求的是起点到终点
    return res;
}

int main()
{
    string start,seq;
    char c;
    for(int i=0;i<=8;++i)
    {
        cin>>c;
        start+=c;
        if(c!='x') seq+=c;
    }
    int cnt=0;  //逆序数,12345678x，
   //123 
   //456 
   //78x   某个数只有上下的移动才会改变逆序数，左右移动是不改变的，改变的逆序数只有+2，或者是-2,逆序数的数量一定是偶数,所以奇数的情况就是无解。

    for(int i=0;i<8;++i)
      for(int j=i;j<8;++j)
         if(seq[i]>seq[j]) cnt++;
    
    if(cnt&1) printf("unsolvable");
    else cout<<astar(start);
    return(0);
}