https://www.luogu.org/problem/P1379
这个代码需要用c++11提交。
#include<bits/stdc++.h> #include<unordered_map> using namespace std; string st; int dx[]={0,0,1,-1},dy[]={1,-1,0,0}; int bfs(){ string ed="123804765"; queue<string> q; unordered_map<string,int> d; q.push(st); d[st]=0; while(!q.empty()){ string t=q.front(); q.pop(); if(t==ed) return d[t]; int distance=d[t]; int k=t.find('0'); int x=k/3,y=k%3; for(int i=0;i<4;i++){ int a=x+dx[i],b=y+dy[i]; if(a>=0&&a<3&&b>=0&&b<3){ swap(t[a*3+b],t[k]); if(!d.count(t)){ q.push(t); d[t]=distance+1; } swap(t[a*3+b],t[k]); } } } return -1; } int main(){ for(int i=0;i<9;i++){ char c; cin>>c; st+=c; } cout<<bfs()<<endl; }