#include <bits/stdc++.h> #define IOSTREAM_BOOST true using namespace std; struct State{ vector<int> val; bool lrotate(int index){ int rightChild = -1; for(int i = index + 1; i < val.size(); i++) if(val[i] == index) rightChild = i; if(rightChild == -1) return false; for(int i = rightChild - 1; i >= 0; i--) if(val[i] == rightChild) return false; val[rightChild] = val[index]; val[index] = rightChild; return true; } bool rrotate(int index){ int leftChild = -1; for(int i = index - 1; i >= 0; i--) if(val[i] == index) leftChild = i; if(leftChild == -1) return false; for(int i = leftChild; i < val.size(); i++) if(val[i] == leftChild) return false; val[leftChild] = val[index]; val[index] = leftChild; return true; } bool operator==(State& other){ return this->val == other.val; } }; struct cmp{ bool operator()(const State &a, const State &b) const{ for(int i = 0; i < a.val.size(); i++) if(a.val[i] != b.val[i]) return a.val[i] < b.val[i]; return false; } }; map<State, int, cmp> dist; int n; vector<int> start; vector<int> finish; State startState, finishState; queue<State> q; void bfs(){ q.push(startState); while(!q.empty()){ State s = q.front(); q.pop(); if(s == finishState) return; for(int i = 0; i < n; i++){ State s2 = s; if(s2.lrotate(i) && !dist.count(s2)){ dist[s2] = dist[s] + 1; q.push(s2); } s2 = s; if(s2.rrotate(i) && !dist.count(s2)){ dist[s2] = dist[s] + 1; q.push(s2); } } } } int main() { #if IOSTREAM_BOOST ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #endif cin >> n; for(int i = 0; i < n; i++){ int a; cin >> a; a--; start.push_back(a); } for(int i = 0; i < n; i++){ int a; cin >> a; a--; finish.push_back(a); } startState = State({start}); finishState = State({finish}); bfs(); if(dist.count(finishState)) cout << dist[finishState] << "\n"; else cout << "-1\n"; return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 | #include <bits/stdc++.h> #define IOSTREAM_BOOST true using namespace std; struct State{ vector<int> val; bool lrotate(int index){ int rightChild = -1; for(int i = index + 1; i < val.size(); i++) if(val[i] == index) rightChild = i; if(rightChild == -1) return false; for(int i = rightChild - 1; i >= 0; i--) if(val[i] == rightChild) return false; val[rightChild] = val[index]; val[index] = rightChild; return true; } bool rrotate(int index){ int leftChild = -1; for(int i = index - 1; i >= 0; i--) if(val[i] == index) leftChild = i; if(leftChild == -1) return false; for(int i = leftChild; i < val.size(); i++) if(val[i] == leftChild) return false; val[leftChild] = val[index]; val[index] = leftChild; return true; } bool operator==(State& other){ return this->val == other.val; } }; struct cmp{ bool operator()(const State &a, const State &b) const{ for(int i = 0; i < a.val.size(); i++) if(a.val[i] != b.val[i]) return a.val[i] < b.val[i]; return false; } }; map<State, int, cmp> dist; int n; vector<int> start; vector<int> finish; State startState, finishState; queue<State> q; void bfs(){ q.push(startState); while(!q.empty()){ State s = q.front(); q.pop(); if(s == finishState) return; for(int i = 0; i < n; i++){ State s2 = s; if(s2.lrotate(i) && !dist.count(s2)){ dist[s2] = dist[s] + 1; q.push(s2); } s2 = s; if(s2.rrotate(i) && !dist.count(s2)){ dist[s2] = dist[s] + 1; q.push(s2); } } } } int main() { #if IOSTREAM_BOOST ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #endif cin >> n; for(int i = 0; i < n; i++){ int a; cin >> a; a--; start.push_back(a); } for(int i = 0; i < n; i++){ int a; cin >> a; a--; finish.push_back(a); } startState = State({start}); finishState = State({finish}); bfs(); if(dist.count(finishState)) cout << dist[finishState] << "\n"; else cout << "-1\n"; return 0; } |