Gena Playing Hanoi Time : O(n * 2^n) Space : O(2^n) 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152int hashOf(vector<int>& A) { int hash = 0; for(int i = 0; i < A.size(); i++) { hash += A[i] << (2 * i); } return hash;}int hanoi(vector<int> posts) { int res = 0; while(!posts.empty() and posts.back() == 1) posts.pop_back(); if(posts.empty()) return 0; unordered_set<long long> us; queue<vector<int>> q; q.push(posts); us.insert(hashOf(posts)); while(!q.empty()) { int sz = q.size(); while(sz--) { auto A = q.front(); q.pop(); int mask = 0, n = A.size(); for(int i = 0; i < n and __builtin_popcount(mask) < 3; i++) { if(mask & (1<< A[i])) continue; mask |= (1 << A[i]); for(int j = 1; j <= 4; j++) { if(mask & (1<<j)) continue; if(i == n - 1 and j == 1) { A.pop_back(); if(A.empty()) return res + 1; int hash = hashOf(A); if(!us.count(hash)) { us.insert(hash); q.push(A); } break; } int o = A[i]; A[i] = j; int hash = hashOf(A); if(!us.count(hash)) { us.insert(hash); q.push(A); } A[i] = o; } } } res++; } return -1;}