0121 - Seven Puzzle
#include <iostream> #include <map> #include <queue> #include <string> #include <utility> using namespace std; const int d[4]={-1, 1, -4, 4}; map<string,int> count; void bfs(void) { queue<string> que; que.push("01234567"); while ( !que.empty() ) { string wk1=que.front(); que.pop(); int pos=wk1.find('0'); for (int i=0; i<4; ++i) if ( 0<=pos+d[i] && pos+d[i]<8 && !(pos==3 && i==1) && !(pos==4 && i==0) ) { string wk2=wk1; swap(wk2[pos],wk2[ pos+d[i] ]); if ( !count[wk2] ) { que.push(wk2); count[wk2]=count[wk1]+1; } } } } void Slove(int n) { string str=""; str+=(n+'0'); for (int i=0; i<7; ++i) { cin >> n; str+=(n+'0'); } cout << count[str]-1 << endl; } int main(void) { int n; count["01234567"]=1; bfs(); while (cin >> n) Slove(n); return 0; }
幅優先探索で最初に全通り試す方法で解きました。