0121:Seven Puzzle
¨01234567¨を作るまでの最短手数。
幅優先探索で¨01234567¨からすべての
状態までの操作回数をmapに作っておく。
#include<iostream> #include<string> #include<algorithm> #include<queue> #include<map> using namespace std; int dx[4]={1,-1,4,-4}; map<string,int>res; void bfs(void){ queue<string>que; que.push("01234567"); while(!que.empty()){ string v=que.front(); que.pop(); int pos=0; for(int i=0;i<8;i++) if(v[i]=='0')pos=i; for(int i=0;i<4;i++){ if(0 <= pos+dx[i] && pos+dx[i]<8 && !(pos==3 && i==0) && !(pos==4 && i==1)){ string u=v; swap(u[pos],u[pos+dx[i]]); if(res[u]==0){ que.push(u); res[u]=res[v]+1; } } } } } int main(void){ int in; res["01234567"]=1; bfs(); while(true){ string s; for(int i=0;i<8;i++){ if(!(cin >> in))return 0; s+=in+'0'; } cout << res[s]-1 << endl; } return 0; }