八数码难题

果然是天才的灵光一现

#include <bits/stdc++.h>
using namespace std;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int bfs(string st)
{map<string,int>m;queue<string>pq;m[st]=0;pq.push(st);while(!pq.empty()){string s=pq.front();int ss=m[s];pq.pop();if(s=="123804765") return ss;int tt=s.find('0');int x=tt/3;int y=tt%3;for(int i=0;i<4;i++){int nx=x+dx[i];int ny=y+dy[i];if(nx<0||nx>=3||ny<0||ny>=3) continue;swap(s[tt],s[nx*3+ny]);if(m.count(s)){swap(s[tt],s[nx*3+ny]);continue;}m[s]=ss+1;pq.push(s);swap(s[tt],s[nx*3+ny]);}}
}
int main()
{string s;cin>>s;cout<<bfs(s)<<endl;
}