图论 八字码

我们可能惊异于某些技巧。我们认为这个技巧真是巧妙啊。或者有人认为我依靠自己的直觉想出了这个表示方法。非常自豪。我认为假设是很小的时候，比如说小学初中，还是不错的。到高中大学，就有一些不成熟了。因为这实际上是一个竞技。很多东西前人其实已经总结得非常全面了。这其实对于高手来说是类似常识一样的东西了。我们得尽快地熟练这些东西。这是最重要的事情。重复。这个是一个非常经典的题。有时间的话，可以多写几遍。像是背英语单词一样。一遍肯定是不够的。

#include<iostream>
#include<algorithm>
#include<queue>
#include<unordered_map>using namespace std;int bfs(string state){queue<string> q;unordered_map<string,int> d;q.push(state);d[state]=0;int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};string end="12345678x";while(q.size()){auto t=q.front();q.pop();if(t==end){return d[t];}int distance=d[t];int k=t.find('x');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[k],t[a*3+b]);if(!d.count(t)){d[t]=distance+1;q.push(t);}swap(t[k],t[a*3+b]);}}}return -1;
}int main(){char s[2];string state;for(int i=0;i<9;i++){cin>>s;state+=*s;}printf("%d\n",bfs(state));return 0;
}