acwing179. 八数码

题目

在一个 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。

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

题解

如果逆序对的数量是奇数个，那么这种情况就无解（证明我也不知道。。）
这里采用A*算法利用曼哈顿距离作为估计值，在估计值的基础上进行搜索会减少不必要的分支，加快搜索效率。

#include <cstring>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>
using namespace std;

int f(string state){
    int res = 0;
    for (int i = 0; i < state.size(); i ++ )
        if (state[i] != 'x'){
            int t = state[i] - '1';
            res += abs(i / 3 - t / 3) + abs(i % 3 - t % 3);
        }
    return res;
}
string bfs(string start){
    int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
    char op[4]={'u','d','l','r'};
    string end="12345678x";
    
    unordered_map<string,int>dist;
    unordered_map<string,pair<string,char>>pre;
    priority_queue<pair<int,string>,vector<pair<int,string>>,greater<pair<int,string>>> heap;
    heap.push({f(start),start});
    dist[start]=0;
    
    while(heap.size()){
        auto t=heap.top();
        heap.pop();
        string state=t.second;
        if(end==state)break;
        int step=dist[state];
        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){
                swap(state[a*3+b],state[x*3+y]);
                if(!dist.count(state)||dist[state]>step+1){
                    dist[state]=step+1;
                    pre[state]={source,op[i]};
                    heap.push({dist[state]+f(state),state});
                }
                swap(state[a*3+b],state[x*3+y]);
            }
        }
        
    }
    string ans;
    while(end!=start){
        ans+=pre[end].second;
        end=pre[end].first;
    }
    reverse(ans.begin(),ans.end());
    return ans;
    
}
int main(){
    string start,end,seq;
    string x;
    while(cin>>x){
        start+=x;
        if(x!="x")seq+=x;
    }
    int t=0;
    for(int i=0;i<seq.size();i++)
        for(int j=i+1;j<seq.size();j++)
            if(seq[j]<seq[i])t++;
    if(t%2)puts("unsolvable");
    else cout<<bfs(start)<<endl;
    
    
    return 0;
}