fork download
copy 
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3. #define inf 1000000
  4. using namespace std;
  5. int curr_state[50],n;
  6. int lim,nlim,result;
  7. int dx[4][4] = {
  8. { -3, -1, +4, -4 },
  9. { +1, +3, +4, -4 },
  10. { +1, -1, +4, -4 },
  11. { +1, -1, +4, -4 }
  12.     };
  13. int manhattan_distance(int p1,int p2);
  14. int dh(int curr_point,int prev_point,int val) //delta
  15. {
  16.     return manhattan_distance(curr_point,val)-manhattan_distance(prev_point,val);
  17. }
  18. int h1()
  19. {
  20.     int h = 0;
  21.     for(int i=1;i<=n;++i)
  22.         h+=manhattan_distance(i,curr_state[i]);
  23.     return h;
  24. }
  25. int parents[50];
  26. bool dfs(int depth,int cost ,int parent,int i)
  27. {
  28.     parents[i] = parent;
  29.     if(depth+cost > lim)
  30.     {
  31.         nlim = min(nlim,depth+cost);
  32.         return false;
  33.     }
  34.     if(!cost){
  35.         result = depth;
  36.         return true;
  37.     }
  38.     int *d = dx[i % 4];
  39.     for (int j = 0; j < 4; j++)
  40.     {
  41.         int k = i + d[j];
  42.         if (k < 1 || k > n || k == parent) continue;
  43.         swap(curr_state[i],curr_state[k]);
  44.         int d = dh(k,i,curr_state[k]) + dh(i,k,curr_state[i]);
  45.         if(dfs(depth+1,cost+d,i,k))
  46.             return true;
  47.         swap(curr_state[i],curr_state[k]);
  48.     }
  49.     return false;
  50. }
  51.  
  52.  
  53.  
  54.  
  55. int IDA_Star(int kings_pos) {
  56.   lim = h1();
  57.   int h = h1();
  58.   while (true) {
  59.     nlim = inf;
  60.     if (dfs(0, h,-1,kings_pos))
  61.       return result;
  62.     if (nlim == inf)
  63.       return -1;
  64.  
  65.     lim = nlim;
  66.   }
  67. }
  68.  
  69. int main()
  70. {
  71.  
  72.     int p1,p2;
  73.     int set_no = 1;
  74.     while(cin>>n && n){
  75.         int kings_pos;
  76.         for(int i=1;i<=n;++i)
  77.         {
  78.  
  79.             cin>>curr_state[i];
  80.             if(curr_state[i] == 1)
  81.                 kings_pos = i;
  82.         }
  83.         cout<<"Set "<<set_no++<<":"<<endl;
  84.         cout<<IDA_Star(kings_pos)<<endl;
  85.  
  86.     }
  87.  
  88.  
  89. }
  90. int manhattan_distance(int p1,int p2)
  91. {
  92.  --p1;
  93.  --p2;
  94. int res = abs(p1%4 - p2%4) + abs(p1/4 - p2/4);
  95.     if((p1%4 == 0 && p2%4 == 3)||(p2%4 == 0 && p1%4 == 3))
  96.     res-=2;
  97. return res;
  98. }
  99.  
  100.  
Time limit exceeded #stdin #stdout 5s 3304KB
comments (?)
stdin
copy 
12
1 11 12 10 9 8 7 6 5 4 3 2
16
9 11 12 10 5 8 7 6 13 4 3 2 1 14 15 16
28
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 26 25 28 27
40
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 26 25 28 27 29 30 31 32 33 34 35 36 38 37 40 39
0
stdout
copy 
Set 1:
36
Set 2:
37
Set 3:
24
Set 4:
https://ideone.com/gVTBMf
language:
C++14 (gcc 8.3)
created:
10 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!