Guest User

Untitled

a guest
Aug 23rd, 2010
77
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <queue>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. int N;
  7.  
  8. struct square{
  9.     char box[20][20];
  10. };
  11.  
  12. struct puzzle{
  13.     square state;
  14.     int steps;
  15.     vector<square> route;
  16.     int xk,yk; //sintetagmenes tou kenou
  17. };
  18.  
  19. bool is_done(square x){
  20.     int num=1;
  21.     bool ok=1;
  22.     for (int i=0;i<N;i++){
  23.         for (int j=0;j<N;j++){
  24.             if ((i==N-1)&&(j==N-1)){
  25.                 num=0;
  26.             }
  27.             if (x.box[i][j]!=num+'0'){
  28.                 ok=0;
  29.             }
  30.             num++;
  31.         }
  32.     }
  33.     return ok;
  34. }
  35.  
  36. void print(square x){
  37.     cout << endl;
  38.     for (int i=0;i<N;i++){
  39.         for (int j=0;j<N;j++){
  40.             cout << x.box[i][j];
  41.         }
  42.         cout << endl;
  43.     }
  44. }
  45.            
  46.  
  47. int main()
  48. {  
  49.     cout << "Dose mou to mikos mias pleuras tou puzzle"<<endl;
  50.     cin >> N;
  51.     cout << "Dose mou to puzzle (sti 8esi tou kenou dose 0)"<< endl;
  52.    
  53.     square a;
  54.     int x,y;
  55.     for (int i=0;i<N;i++){
  56.         for (int j=0;j<N;j++){
  57.             cin >> a.box[i][j];
  58.             if (a.box[i][j]=='0'){
  59.                 x=i;
  60.                 y=j;
  61.             }
  62.         }
  63.     }
  64.                
  65.     puzzle init;
  66.     init.state=a;
  67.     init.steps=0;
  68.     init.route.push_back(a);
  69.     init.xk=x;
  70.     init.yk=y;
  71.    
  72.     queue<puzzle> q;
  73.     q.push(init);
  74.     bool ok=0;
  75.     puzzle temp1,temp2;
  76.     int moves=0;
  77.    
  78.     while ((!q.empty())&&(ok==0)){
  79.         temp1=q.front();
  80.         q.pop();
  81.         if ((temp1.xk==N-1)&&(temp1.yk==N-1)){ //elegxw an to puzzle lithike
  82.             if (is_done(temp1.state)){
  83.                 ok=1;
  84.                 cout<< endl <<"H lisi vre8ike se: "<< temp1.steps<<" vimata" << endl;
  85.                 for (int i=0;i<temp1.route.size();i++){
  86.                     print(temp1.route[i]);
  87.                 }
  88.             }
  89.         }
  90.        
  91.         if (ok==0){ //an dn li8ike prepei na proxwrisw se epomeni katastasi
  92.             if (temp1.xk<N-1){ //mporw na metakinisw ena tetragwnaki pros ta panw
  93.                 temp2.state=temp1.state;
  94.                 temp2.state.box[temp1.xk][temp1.yk]=temp2.state.box[temp1.xk+1][temp1.yk]; //metakinw to koutaki
  95.                 temp2.state.box[temp1.xk+1][temp1.yk]='0';
  96.                 temp2.steps=temp1.steps+1;
  97.                 temp2.route=temp1.route;
  98.                 temp2.route.push_back(temp2.state);
  99.                 temp2.xk=temp1.xk+1;
  100.                 temp2.yk=temp1.yk;
  101.                 q.push(temp2);
  102.             }
  103.             if (temp1.xk>0){ //mporw na metakinisw ena tetragwnaki pros ta katw
  104.                 temp2.state=temp1.state;
  105.                 temp2.state.box[temp1.xk][temp1.yk]=temp2.state.box[temp1.xk-1][temp1.yk]; //metakinw to koutaki
  106.                 temp2.state.box[temp1.xk-1][temp1.yk]='0';
  107.                 temp2.steps=temp1.steps+1;
  108.                 temp2.route=temp1.route;
  109.                 temp2.route.push_back(temp2.state);
  110.                 temp2.xk=temp1.xk-1;
  111.                 temp2.yk=temp1.yk;
  112.                 q.push(temp2);
  113.             }
  114.             if (temp1.yk<N-1){ //mporw na metakinisw ena tetragwnaki pros ta aristera
  115.                 temp2.state=temp1.state;
  116.                 temp2.state.box[temp1.xk][temp1.yk]=temp2.state.box[temp1.xk][temp1.yk+1]; //metakinw to koutaki
  117.                 temp2.state.box[temp1.xk][temp1.yk+1]='0';
  118.                 temp2.steps=temp1.steps+1;
  119.                 temp2.route=temp1.route;
  120.                 temp2.route.push_back(temp2.state);
  121.                 temp2.xk=temp1.xk;
  122.                 temp2.yk=temp1.yk+1;
  123.                 q.push(temp2);
  124.             }
  125.             if (temp1.yk>0){ //mporw na metakinisw ena tetragwnaki pros ta deksia
  126.                 temp2.state=temp1.state;
  127.                 temp2.state.box[temp1.xk][temp1.yk]=temp2.state.box[temp1.xk][temp1.yk-1]; //metakinw to koutaki
  128.                 temp2.state.box[temp1.xk][temp1.yk-1]='0';
  129.                 temp2.steps=temp1.steps+1;
  130.                 temp2.route=temp1.route;
  131.                 temp2.route.push_back(temp2.state);
  132.                 temp2.xk=temp1.xk;
  133.                 temp2.yk=temp1.yk-1;
  134.                 q.push(temp2);
  135.             }
  136.         }
  137.     }          
  138.    
  139.     return 0;
  140. }
RAW Paste Data