fork(3) download
copy 
  1. /*__ _(_) __ _  ___  ___ _   _  __| | __ _ _   _| |_ ___
  2.  / _` | |/ _` |/ _ \/ __| | | |/ _` |/ _` | | | | __/ _ \
  3. | (_| | | (_| | (_) \__ \ |_| | (_| | (_| | |_| | || (_) |
  4.  \__, |_|\__,_|\___/|___/\__,_|\__,_|\__,_|\__,_|\__\___/
  5.  |___/                                  Accepted Code  */
  6.  
  7. #include<bits/stdc++.h>
  8. using namespace std;
  9.  
  10. int maxint=1e9+7;
  11. int n=12;
  12. int he[12][12];
  13. int a[12];
  14. vector<int> ke[12];
  15. int res,solved;
  16.  
  17.  
  18. void init_edge()
  19. {
  20.     int dk[]= {1,3,6,12};
  21.     for(int i=0; i<12; i++)
  22.     {
  23.         for(int j=i+1; j<12; j++)
  24.         {
  25.             he[i][j]=he[j][i]=maxint;
  26.             bool ok=false;
  27.             int k=0;
  28.             for(k=0; k<4; k++)
  29.                 if(abs(i-j)==dk[k])
  30.                 {
  31.                     ok=true;
  32.                     break;
  33.                 }
  34.             if(!ok) continue;
  35.             int sc=dk[k+1];
  36.             if(floor(i/sc)==floor(j/sc))
  37.             {
  38.                 ke[i].push_back(j);
  39.                 ke[j].push_back(i);
  40.                 he[i][j]=he[j][i]=1;
  41.             }
  42.         }
  43.         he[i][i]=0;
  44.     }
  45. }
  46.  
  47. void init_he()
  48. {
  49.     for(int k=0; k<n; k++)
  50.         for(int i=0; i<n; i++)
  51.             for(int j=0; j<n; j++)
  52.                 he[i][j]=min(he[i][j],he[i][k]+he[k][j]);
  53. }
  54.  
  55. inline int DFS(int cur,int pre,int sum_he,int dep)
  56. {
  57.     if(sum_he==0)
  58.     {
  59.         solved=dep;
  60.         return solved;
  61.     }
  62.  
  63.     if(dep+sum_he>res) return dep+sum_he;
  64.     int res2=maxint;
  65.     int save_he=sum_he;
  66.  
  67.     for(int j:ke[cur])
  68.     {
  69.         if(j==pre) continue;
  70.         sum_he-=he[j][a[j]];
  71.         swap(a[cur],a[j]);
  72.         sum_he+=he[cur][a[cur]];
  73.         int tmp=DFS(j,cur,sum_he,dep+1);
  74.         if(solved!=0) return solved;
  75.         sum_he=save_he;
  76.         swap(a[cur],a[j]);
  77.         res2=min(tmp,res2);
  78.     }
  79.     return res2;
  80. }
  81.  
  82. void solve()
  83. {
  84.     int l0;
  85.     for(int i=0; i<12; i++) cin>>a[i],a[i]==0?l0=i:1;
  86.  
  87.     res=0;
  88.     int sum_he=0;
  89.     for(int i=0; i<12; i++) i==l0?1:sum_he+=he[i][a[i]];
  90.     if(sum_he==0)
  91.     {
  92.         cout<<0<<endl;
  93.         return;
  94.     }
  95.  
  96.     solved=0;
  97.     res=sum_he;
  98.     while (solved==0)
  99.     {
  100.         res=DFS(l0,-1,sum_he,0);
  101.     }
  102.     cout<<solved<<endl;
  103. }
  104.  
  105. int main()
  106. {
  107.     init_edge();
  108.     init_he();
  109.     int T;
  110.     cin>>T;
  111.     while(T--) 
  112. 		solve();
  113.     return 0;
  114. }
  115.  
Success #stdin #stdout 0s 3464KB
comments (?)
stdin
copy 
2
1 10 2 3 0 5 7 4 8 6 9 11
6 4 1 0 3 5 9 7 2 10 11 8
stdout
copy 
8
9
https://ideone.com/7BrHEe
NK05EOPR - Đổi chỗ
language:
C++14 (gcc 8.3)
created:
7 years 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!