fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll long long
  6. #define value first
  7. #define index second
  8.  
  9. #define EGRY                          \
  10.     ios_base::sync_with_stdio(false); \
  11.     cin.tie(NULL);
  12.  
  13. const int MAX = 2 * 1e5 + 1000;
  14. const int MOD = 1e9 + 7;
  15. const int OO = INT_MAX;
  16.  
  17. const double EPS = (double)1e-9;
  18.  
  19. bitset<1000000000> visited;
  20.  
  21. vector<vector<int>> matrix(3, vector<int>(3));
  22. int target = 123456789;
  23.  
  24. ll encode(vector<vector<int>> &matrix)
  25. {
  26.     ll num = 0;
  27.  
  28.     for (int i = 0; i < 3; i++)
  29.     {
  30.         for (int j = 0; j < 3; j++)
  31.         {
  32.             num = num * 10 + matrix[i][j];
  33.         }
  34.     }
  35.  
  36.     return num;
  37. }
  38.  
  39. ll bfs()
  40. {
  41.     queue<vector<vector<int>>> q;
  42.     q.push(matrix);
  43.  
  44.     ll level = 0, size = 1;
  45.     visited.set(encode(matrix));
  46.  
  47.     while (!q.empty())
  48.     {
  49.         while (size--)
  50.         {
  51.             vector<vector<int>> cur_matrix = q.front();
  52.             q.pop();
  53.  
  54.             if (encode(cur_matrix) == target)
  55.             {
  56.                 return level;
  57.             }
  58.  
  59.             for (int i = 0; i < 2; i++)
  60.             {
  61.                 for (int j = 0; j < 3; j++)
  62.                 {
  63.                     swap(cur_matrix[i][j], cur_matrix[i + 1][j]);
  64.                     int state = encode(cur_matrix);
  65.                     if (!visited.test(state))
  66.                     {
  67.                         visited.set(state);
  68.                         q.push(cur_matrix);
  69.                     }
  70.                     swap(cur_matrix[i][j], cur_matrix[i + 1][j]);
  71.                 }
  72.             }
  73.  
  74.             for (int i = 0; i < 3; i++)
  75.             {
  76.                 for (int j = 0; j < 2; j++)
  77.                 {
  78.                     swap(cur_matrix[i][j], cur_matrix[i][j + 1]);
  79.                     int state = encode(cur_matrix);
  80.                     if (!visited.test(state))
  81.                     {
  82.                         visited.set(state);
  83.                         q.push(cur_matrix);
  84.                     }
  85.                     swap(cur_matrix[i][j], cur_matrix[i][j + 1]);
  86.                 }
  87.             }
  88.         }
  89.         size = (ll)q.size(), level++;
  90.     }
  91.  
  92.     return -1;
  93. }
  94.  
  95. void solve()
  96. {
  97.  
  98.     for (int i = 0; i < 3; i++)
  99.     {
  100.         for (int j = 0; j < 3; j++)
  101.         {
  102.             cin >> matrix[i][j];
  103.         }
  104.     }
  105.  
  106.     cout << bfs();
  107. }
  108.  
  109. int main()
  110. {
  111.     EGRY
  112.         ll t = 1;
  113.     // cin >> t;
  114.  
  115.     while (t--)
  116.     {
  117.         solve();
  118.     }
  119.  
  120.     return 0;
  121. }
Success #stdin #stdout 0s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/Vt978Z
language:
C++14 (gcc 8.3)
created:
6 days ago
visibility:
public

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!