题目描述
在一个?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×33×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
思路
首先，八数码有解判断的必要条件：逆序对的个数若为偶数个时有解，若为奇数个则无解。详见图（借，有问题则删，https://www.acwing.com/solution/content/35528/）
其次，对于使用astar优化时，因为当我们移动一个点的时候，只能上下左右间移动，因此 f(n) 预估距离的设定，这里定义为当前图各个点到最终图各个点的哈夫曼距离之和。
参考代码：
#include <bits/stdc++.h>
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define LL long long
#define x first
#define y second
#define PII pair<int,int>
#define PIS pair<int,string>
#define PIII pair<int,PII>
#define PDD pair<double,double>
using namespace std;
const int INF=0x3f3f3f3f;
const int N=1005;
const int M=1e7;
const int mod=1e9+7;
/*
八数码有解判断的必要条件：逆序对的个数若为偶数个时有解，若为奇数个则无解。
*/
//当前点到终点的预估距离，每个位置点距离自己正确位置的哈夫曼距离和
// abs(xs-xe)+abs(ys-ye);
int f(string state)
{
int res = 0;
int len=state.length();
for(int i=0;i<len;i++)
{
if(state[i] != 'x')
{
int t = state[i] - '1';
res += abs(i/3 - t/3)+abs(i%3 - t%3);
}
}
return res;
}
string start; //存初始状态
int dir[4][2]={-1,0,1,0,0,-1,0,1};
char go[]="udlr";
string astar()
{
//最终状态
string end="12345678x";
map<string , int> dis; //到这个状态的实际距离
map<string , pair<string,char> >pre; //到这个状态的,前个状态和动作
priority_queue<PIS,vector<PIS>,greater<PIS> >q;
q.push({f(start),start});
dis[start]=0;
while(q.size())
{
auto tmp=q.top();
q.pop();
//当前状态
string state=tmp.y;
//到达最终状态，退出
if(state==end)break;
//获取当前步数
int step=dis[state];
int x,y;
//找到操作"X"的位置
for(int i=0;i<9;i++)
{
if(state[i]=='x')
{
x=i/3;
y=i%3;
break;
}
}
//存储当前状态
string source=state;
//开始向4个方向扩展
for(int i=0,nx,ny;i<4;i++)
{
nx=x+dir[i][0];
ny=y+dir[i][1];
if(nx<0 || nx>=3 || ny<0 || ny>=3)continue;
//交换2点位置
swap(state[x*3+y],state[nx*3+ny]);
/*
更新状态的2种情况:
1.若移动后的状态不存在
2.若移动后的状态所用步数大于当前状态，则表示移动后的状态下都可以被更新
*/
if(dis.count(state)==0 || dis[state]>step+1)
{
//更新实际距离
dis[state]=step+1;
//记录前驱,{前一个状态，动作}
pre[state]={source,go[i]};
q.push({dis[state]+f(state),state});
}
//回溯2点位置
swap(state[x*3+y],state[nx*3+ny]);
}
}
//反向遍历操作结果
string res="";
while(end!=start)
{
res+=pre[end].y;
end=pre[end].x;
}
reverse(res.begin(),res.end());
return res;
}
int main()
{
char c;
string str; //用来判断逆序对
for(int i=0;i<9;i++)
{
cin>>c;
if(c!='x')str+=c;
start+=c;
}
int cnt=0; //逆序对个数
for(int i=0;i<str.length();i++)
{
for(int j=i+1;j<str.length();j++)
{
if(str[i]>str[j])cnt++;
}
}
//奇数个，无解
if(cnt&1)cout<<"unsolvable\n";
//偶数个，存在解
else cout<<astar()<<"\n";
system("pause");
return 0;
}
