AcWing 179. 八数码
原题链接
中等
作者:
Isaacs
,
2022-02-28 20:40:50
,
所有人可见
,
阅读 159
看过y总的视频后过来打卡,有些设计定义一开始没看懂,写好注释共享出来
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <unordered_map>
using namespace std;
typedef pair<int,string> PIS;
//四个方向
int mx[4] = {-1, 0, 1, 0}, my[4] = {0, 1, 0, -1};
char op[10] = "urdl";
//计算当前状态到终点的曼哈顿距离
int manhattan(string str){
int sum=0;
for(int i=0;i<9;i++){
if(str[i]=='x'){
;
}else{
int k=str[i]-'1';//将数据str[i](1-8转化为0-7)
sum+=abs(i/3-k/3)+abs(i%3-k%3);
}
}
return sum;
}
string bfs(string first){
//初始化
string end = "12345678x";
unordered_map<string,int> d;//原点到当前状态的总步数
unordered_map<string,pair<string,char>> last;//使用这个map存这个string上一步的string和操作步骤
priority_queue<PIS, vector<PIS>, greater<PIS>> heap;//小根堆,将元素的估计终点距离从小到大排序
heap.push({manhattan(first),first});
d[first]=0;//初始情况步数为0
while(heap.size()>0){
PIS a=heap.top();
heap.pop();
string state=a.second;//获取当前的取出来的状态字符串,可以把当前状态看作为一个中转站。
//如起点为a,中间点为x,终点为b. s(xy)表示x-y的步数,
//则s(ab)=s(ax)+s(ay);用向量的思想很好理解。
if(state==end)break;
int m,n;//当前状态空白字符的位置
for (int j = 0; j < 9; j ++ ){
if(state[j]=='x'){
m=j/3;//行坐标
n=j%3;//列坐标
}
}
string tmp=state;
for (int i = 0; i < 4; i ++ ){
int m1=m+mx[i];
int n1=n+my[i];
if((0<=m1&&m1<3)&&(0<=n1&&n1<3)){
state=tmp;//还原state
swap(state[m * 3 + n], state[m1 * 3 + n1]);
if(!d.count(state)||d[state]>d[tmp]+1){
d[state]=d[tmp]+1;
last[state]={tmp,op[i]};
heap.push({manhattan(state)+d[state],state});
}
}else{
//越界
continue;
}
}
}
string result="";
string endstr=end;
//通过使用last推出步骤
while(endstr!=first){
result+=last[endstr].second;
endstr=last[endstr].first;
}
reverse(result.begin(),result.end());
return result;
}
int main()
{
string first,judge;
char c;
while (cin >> c){
first+=c;
if(c!='x'){
judge+=c;
}
}
int cnt=0;
for (int i = 0; i < 8; i ++ ){
for (int j = i+1; j < 8; j ++ ){
if(judge[i]>judge[j]){
cnt++;
}
}
}
if(cnt%2){
cout<<"unsolvable";
}else{
cout<<bfs(first);
}
return 0;
}