fork download
copy 
  1. #include<bits/stdc++.h> 
  2. using namespace std; 
  3. #define endl "\n" 
  4. #define fi first 
  5. #define se second 
  6. #define tn int
  7. #define thaonguyen( i, a, b ) for( tn i = a; i <= b; i++ )
  8. #define nguyenthao( i, a, b ) for( tn i = a; i >= b; i-- )
  9. #define thaonguyenxinh ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
  10. char chr;
  11. tn cost;
  12. string s, u; 
  13. queue< pair< string, tn > > q;
  14. unordered_set< string > st; 
  15. void move( tn position, tn type ){
  16.     if ( type == 1 ){
  17.         if ( position != 2 and position != 5 and position != 8 ){
  18.            swap( u[position], u[position+1] );
  19.             if ( st.find( u ) == st.end() ){
  20.                     st.insert(u);
  21.                     q.push( { u, cost + 1 } );
  22.                 } 
  23.             swap( u[position], u[position+1] );
  24.         }
  25.     }
  26.     if ( type == 2 ){
  27.         if ( position != 0 and position != 3 and position != 6 ){
  28.             swap( u[position], u[position-1] );
  29.             if ( st.find( u ) == st.end() ){
  30.                     st.insert(u);
  31.                     q.push( { u, cost + 1 } );
  32.                 } 
  33.            swap( u[position], u[position-1] );
  34.         }
  35.     }
  36.     if ( type == 3 ){
  37.         if ( position != 6 and position != 7 and position != 8 ){
  38.            swap( u[position], u[position+3] );
  39.             if ( st.find( u ) == st.end() ){
  40.                     st.insert(u);
  41.                     q.push( { u, cost + 1 } );
  42.                 } 
  43.             swap( u[position], u[position+3] );
  44.         }
  45.     }
  46.     if ( type == 4 ){
  47.         if ( position != 0 and position != 1 and position != 2 ){
  48.             swap( u[position], u[position - 3] );
  49.             if ( st.find( u ) == st.end() ){
  50.                     st.insert(u);
  51.                     q.push( { u, cost + 1 } );
  52.                 } 
  53.             swap( u[position], u[position - 3] );
  54.         }
  55.     }
  56. }
  57. void cfs(){
  58.     q.push( { s , 0 } );
  59.     while ( !q.empty() ){
  60.         u = q.front().fi; 
  61.         cost = q.front().se;
  62.         if ( u == "123456789" ){
  63.             cout << q.front().se; 
  64.             break;
  65.         }
  66.         q.pop(); 
  67.         thaonguyen( i, 0, s.size() - 1 )
  68.             thaonguyen( j, 1, 4 ){
  69.                 move( i, j );
  70.  
  71.             }
  72.     }
  73. }
  74. signed main(){
  75.     thaonguyenxinh
  76.     thaonguyen( i, 1, 9 )
  77.         cin >> chr, 
  78.         s += chr;
  79.     st.insert(s);
  80.     cfs();
  81. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/yKneg6
language:
C++14 (gcc 8.3)
created:
21 hours ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!