fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define pb push_back
  4. #define pii pair<int, int>
  5. #define fi first
  6. #define se second
  7. #pragma GCC optimize("03,unroll-loops")
  8. #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  9. using namespace std;
  10. const int MOD = 1e9 + 7;
  11.  
  12. struct Node {
  13.     string cur;
  14.     int cnt;
  15. };
  16.  
  17. string trai(string s)
  18. {
  19.     string t = s;
  20.     t[0] = s[3];
  21.     t[1] = s[0];
  22.     t[8] = s[5];
  23.     t[5] = s[1];
  24.     t[7] = s[8];
  25.     t[3] = s[7];
  26.     return t;
  27. }
  28. string phai(string s)
  29. {
  30.     string t = s;
  31.     t[1] = s[4];
  32.     t[2] = s[1];
  33.     t[6] = s[2];
  34.     t[9] = s[6];
  35.     t[8] = s[9];
  36.     t[4] = s[8];
  37.     return t;
  38. }
  39. string trai1(string s)
  40. {
  41.     string t = s;
  42.     t[3] = s[0];
  43.     t[0] = s[1];
  44.     t[5] = s[8];
  45.     t[1] = s[5];
  46.     t[8] = s[7];
  47.     t[7] = s[3];
  48.     return t;
  49. }
  50. string phai1(string s)
  51. {
  52.     string t = s;
  53.     t[4] = s[1];
  54.     t[1] = s[2];
  55.     t[2] = s[6];
  56.     t[6] = s[9];
  57.     t[9] = s[8];
  58.     t[8] = s[4];
  59.     return t;
  60. }
  61. string dich = "1238004765";
  62. string st ="";
  63. int BFS()
  64. {
  65.     queue<string> q;
  66.     unordered_map<string, int> m;
  67.     q.push(st);
  68.     m[st] = 0;
  69.     while (!q.empty())
  70.     {
  71.         string p = q.front();
  72.         q.pop();
  73.         int dem = m[p] + 1;
  74.         string l = trai(p);
  75.         if (!m[l])
  76.         {
  77.             m[l] = dem;
  78.             q.push(l);
  79.         }
  80.         string r = phai(p);
  81.         if (!m[r])
  82.         {
  83.             m[r] = dem;
  84.             q.push(r);
  85.         }
  86.         if (dem == 14) break;
  87.     }
  88.     queue<string> q1;
  89.     unordered_map<string, int> mp;
  90.     q1.push(dich);
  91.     mp[dich] = 0;
  92.     int ans = MOD;
  93.     while (!q1.empty())
  94.     {
  95.         string p = q1.front();
  96.         q1.pop();
  97.         if (m[p] && ans > m[p] + mp[p]) ans = m[p] + mp[p];
  98.         int dem = mp[p] + 1;
  99.         string l = trai1(p);
  100.         if (!mp[l])
  101.         {
  102.             mp[l] = dem;
  103.             q1.push(l);
  104.         }
  105.         string r = phai1(p);
  106.         if (!mp[r])
  107.         {
  108.             mp[r] = dem;
  109.             q1.push(r);
  110.         }
  111.         if (dem == 14) break;
  112.     }
  113.     return ans;
  114. }
  115. int main()
  116. {
  117.     ios_base::sync_with_stdio(0);
  118.     cin.tie(0); cout.tie(0);
  119.     for (int i=0; i<10; ++i) 
  120.     {
  121.         int x;
  122.         cin >> x;
  123.         st += to_string(x);
  124.     }
  125.     cout << BFS();
  126. }
Success #stdin #stdout 0.02s 6704KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1000000007
https://ideone.com/RkwqZp
language:
C++14 (gcc 8.3)
created:
21 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!