Aizu Online Judge 0121 seven puzzle
mapのkeyとしてvector
#include<iostream> #include<vector> #include<queue> #include<map> using namespace std; vector<int> va(8); int main(){ vector<int> vec(8); for(int i = 0; i < 8; i++) vec[i] = i; map<vector<int>, int> mpa; queue<vector<int> > qa; mpa[vec] = 1; qa.push(vec); while(!qa.empty()){ vector<int> vb = qa.front(); qa.pop(); for(int i = 0; i < 8; i++){ if(vb[i] == 0){ if(i != 0 && i != 4){ vector<int> vc = vb; swap(vc[i], vc[i - 1]); if(mpa[vc] == 0){ mpa[vc] = mpa[vb] + 1; qa.push(vc); } } if(i != 3 && i != 7){ vector<int> vc = vb; swap(vc[i], vc[i + 1]); if(mpa[vc] == 0){ mpa[vc] = mpa[vb] + 1; qa.push(vc); } } if(i >= 0 && i <= 3){ vector<int> vc = vb; swap(vc[i], vc[i + 4]); if(mpa[vc] == 0){ mpa[vc] = mpa[vb] + 1; qa.push(vc); } } if(i >= 4 && i <= 7){ vector<int> vc = vb; swap(vc[i], vc[i - 4]); if(mpa[vc] == 0){ mpa[vc] = mpa[vb] + 1; qa.push(vc); } } } } } while(cin >> va[0]){ for(int i = 1; i < 8; i++) cin >> va[i]; cout << mpa[va] - 1 << endl; } return 0; }