Untitled
unknown
plain_text
7 months ago
2.7 kB
16
Indexable
Never
#include<bits/stdc++.h> using namespace std; typedef long long int ll; #define int ll #define set set<int> #define uset unordered_set<int> #define veci vector<int> #define vecs vector<string> #define stack stack<int> #define pb push_back #define mp make_pair #define pii pair<int,int> #define all(x) (x).begin(), (x).end() #define FOR(s,n) for(int i = s; i < n; i++) template<typename T> ostream& operator<<(ostream& COUT, vector<T>& v){ for(int i=0 ; i<v.size() ; i++){ COUT<<v[i]<<" "; } COUT << endl; return COUT; } template<typename T> istream& operator>>(istream& CIN, vector<T>& a){ for(int i=0 ; i<a.size() ; i++) CIN>>a[i]; return CIN; } template<typename T> void pws(const T& arg){ cout << arg <<endl;} template <typename T, typename... Args> void pws(const T& first, const Args&... args) {cout << first << " ";pws(args...);} int dir[8][2] = {{0,1},{1,0},{-1,0},{0,-1},{1,1},{-1,1},{1,-1},{-1,-1}}; int MOD = 1e9 + 7; int n,m,k; void solve(){ string s; for(int i=0;i<9;i++){ int x; cin>>x; s+=(char)(x+'0'); } string target = "123456789"; queue<pair<string,int>> q; // source is s q.push({s,0}); unordered_map<string,int> vis; // 9! = 3,62,880 possible state of cube possible vis[s] = 1; while(!q.empty()){ auto [str,d] = q.front();q.pop(); if(str==target) { cout<<d<<endl; break; } string temp = str; // for horizontal swap possiblity for(int i=0;i<2;i++){ swap(temp[i],temp[i+1]); if(!vis[temp]){ vis[temp] = 1; q.push({temp,d+1}); } swap(temp[i],temp[i+1]); } for(int i=3;i<5;i++){ swap(temp[i],temp[i+1]); if(!vis[temp]){ vis[temp] = 1; q.push({temp,d+1}); } swap(temp[i],temp[i+1]); } for(int i=6;i<9;i++){ swap(temp[i],temp[i+1]); if(!vis[temp]){ vis[temp] = 1; q.push({temp,d+1}); } swap(temp[i],temp[i+1]); } // for veritical swap possiblity for(int i=0;i<6;i++){ swap(temp[i],temp[i+3]); if(!vis[temp]){ vis[temp] = 1; q.push({temp,d+1}); } swap(temp[i],temp[i+3]); } } } signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int t=1; // cin>>t; while(t--) solve(); }