fork download
copy 
  1. using namespace std;
  2. #include <bits/stdc++.h>
  3.  
  4. #define MAX 100100
  5. #define MOD 1000000007
  6. #define PI 3.1415926535897932384
  7. #define F first
  8. #define S second
  9. #define pb push_back
  10. #define mp make_pair
  11. #define endl "\n"
  12. typedef long long ll;
  13. typedef unsigned long long ull;
  14.  
  15. vector<int> vals;
  16. map<int, int> mym;
  17. queue<pair<vector<int>, int> > myq;
  18.  
  19. int get_key(vector<int> vet){
  20.     int acm = 0, mul = 1;
  21.  
  22.     for(int i = 0;i < vet.size();i++){
  23.         acm += vet[i]*mul;
  24.         mul *= 10;
  25.     }
  26.  
  27.     return acm;
  28. }
  29.  
  30. void f(){
  31.     int i;
  32.  
  33.     for(int i = 1;i < 9;i++) vals.pb(i);
  34.     vals.pb(0);
  35.  
  36.     myq.push(mp(vals, 1));
  37.  
  38.     while(!myq.empty()){
  39.         vector<int> vet = myq.front().F;
  40.         int p = myq.front().S, id = get_key(vet);
  41.  
  42.         myq.pop();
  43.  
  44.         if(mym[id]) continue;
  45.  
  46.         for(i = 0;i < vet.size();i++){
  47.             if(!vet[i]) break;
  48.         }
  49.  
  50.         mym[id] = p;
  51.  
  52.         if(i != 0 && i != 3 && i != 6){
  53.             swap(vet[i], vet[i-1]);
  54.             if(!mym[get_key(vet)]) myq.push(mp(vet, p+1));
  55.             swap(vet[i], vet[i-1]);
  56.         }
  57.         if(i > 2){
  58.             swap(vet[i], vet[i-3]);
  59.             if(!mym[get_key(vet)]) myq.push(mp(vet, p+1));
  60.             swap(vet[i], vet[i-3]);
  61.         }
  62.         if(i != 2 && i != 5 && i != 8){
  63.             swap(vet[i], vet[i+1]);
  64.             if(!mym[get_key(vet)]) myq.push(mp(vet, p+1));
  65.             swap(vet[i], vet[i+1]);
  66.         }
  67.         if(i < 6){
  68.             swap(vet[i], vet[i+3]);
  69.             if(!mym[get_key(vet)]) myq.push(mp(vet, p+1));
  70.             swap(vet[i], vet[i+3]);
  71.         }
  72.     }
  73.  
  74.     return;
  75. }
  76.  
  77. int main(){
  78.     //freopen("in", "r", stdin);
  79.     //freopen("out", "w", stdout);
  80.  
  81.     f();
  82.  
  83.     int t;
  84.     cin >> t;
  85.  
  86.     for(int test = 1;test <= t;test++){
  87.         for(int i = 0;i < 9;i++) scanf("%d", &vals[i]);
  88.  
  89.         int aux = mym[get_key(vals)];
  90.  
  91.         cout << "Case " << test << ": ";
  92.         if(!aux) cout << "impossible" << endl;
  93.         else cout << aux-1 << endl;
  94.     }
  95.  
  96.     return 0;
  97. }
  98.  
Success #stdin #stdout 0.43s 10208KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Case 1: 0
https://ideone.com/kq4ph5
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!