这道题目是移动矩阵中的’x’使得最后得到的矩阵序列展开是”12345678x”,也即八数码。八数码是否有解是看逆序对的数目是否是偶数,为奇数则无解。这道题目就可以现根据逆序对的数目先快速的判断题目是否有解,无解则停止,否则进行下一步。题目中定义了dist、st、prev
和heap
分别来表示每个状态下到达目标状态的曼哈顿距离、当前状态是否被搜过、记录下方案,存储当前状态的上一个状态是什么以及从上一个状态变到当前状态的操作是什么、以及优先队列。
题目中首先计算初始状态到目标状态的曼哈顿距离并存到优先队列heap中,记录当前状态下的曼哈顿距离是0;然后进入循环直到优先队列heap为空。在优先队列中取出一个顶元素,用state
接受,特判如果state==end
就直接退出,否则进行后续。再找到x在矩阵中的坐标,每次试探性的向上、向下、向左、向右的移动一次,如果得到的距离比之前的距离小则存下当前状态,直到退出循换。然后再回溯状态,如果当前end不是初始输入的start
状态的话,就不停的回溯,并且记录下回溯的操作,直到end==start
,这时候得到的状态字符串是逆序的,对该字符串倒序一下并返回即可
#include<bits/stdc++.h>
using namespace std;
int f(string state){//A*算法,存储的是每一个点到目标距离的曼哈顿距离
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[] = {-1,0,1,0},dy[] = {0,1,0,-1};
char op[] = {'u','r','d','l'};
string end = "12345678x";
unordered_map<string,int>dist;//记录距离,当前需要多少步操作
unordered_map<string,bool>st;//记录每一个状态是否被搜过
unordered_map<string,pair<string,char>>prev;//记录方案,存下上个状态是什么以及从上一个状态变到当前状态进行的操作是什么
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(state==end)break;//特判,防止超时
if(st[state])continue;//记录当前状态是否已经出过队,出过则继续循环,
st[state] = true;//否则进行标记
int step = dist[state];
int x,y;//求的是当前 'x' 的位置
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 = dx[i]+x,b = dy[i]+y;
if(a>=0&&a<3&&b>=0&&b<3){
swap(state[x*3+y],state[a*3+b]);//先交换一次位置
if(!dist.count(state)||dist[state]>step+1){//如果当前状态不存在或者当前状态的曼哈顿距离>step+1
dist[state] = step+1;//更新距离
prev[state] = {source,op[i]};//加入到当前状态以及操作
heap.push({dist[state]+f(state),state});//将当前小距离+到达目标状态的曼哈顿距离以及当前状态压入到优先队列中
}
swap(state[x*3+y],state[a*3+b]);//再交换一次位置
}
}
}
string res;
while(end!=start){
res+=prev[end].second;//从后往前依次记录下每个操作
end = prev[end].first;//更新当前end状态
}
reverse(res.begin(),res.end());
return res;
}
int main(){
string c,g,seq;
while(cin>>c){
g+=c;
if(c!="x")seq = seq + c;
}
int t = 0;
for(int i = 0;i<seq.size();i++){
for(int j = i+1;j<seq.size();j++){
if(seq[i]>seq[j])t++;
}
}
if(t%2)puts("unsolvable");
else cout<<bfs(g);
return 0;
}