https://www.acwing.com/problem/content/847/
本质还是bfs。状态通过字符串(一维保存方法),在转移时通过计算变成二维状态
标记数组通过unorder_map实现
#include <iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#include<unordered_map>
using namespace std;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int ans=-1;
int bfs(string start){
string end="12345678x";
queue<string>q;
unordered_map<string,int>dist;
q.push(start);
dist[start]=0;
while(q.size()){
auto t=q.front();
q.pop();
int temp=dist[t];
if(t==end){
return ans=temp;
}
int k=t.find(‘x‘);//找到x的一维坐标
int x=k/3;//将一维坐标转化成二维坐标
int y=k%3;
for(int i=0;i<4;i++){
int a=x+dx[i];
int b=y+dy[i];
if(a>=0 && a<3 && b>=0 &&b<3){
int nk=a*3+b;//二维坐标转化成一维坐标
swap(t[k],t[nk]);
if(!dist.count(t)){
dist[t]=temp+1;
q.push(t);
}
swap(t[k],t[nk]);
}
}
}
}
int main(){
string start;
for(int i=0;i<9;i++){
char c;
cin>>c;
start+=c;
}
bfs(start);
cout<<ans;
return 0;
}
// freopen("testdata.in", "r", stdin);