fork download
copy 
  1. #pragma comment (linker, "/STACK:64000000");
  2. #include<iostream>
  3. #include<string>
  4. #include <fstream>
  5. #include <ctime>
  6. #include <cstdlib>
  7. #include <algorithm>
  8. #include <map>
  9. #include <vector>
  10. using namespace std;
  11. const int N=3;
  12. int a[N][N], t, b[N*N];
  13. int X,Y;
  14. string M="";
  15. map<string,bool> map1;
  16. vector<string>  answers;
  17. bool chek(int b[N][N])
  18. {
  19.     int k=1;
  20.     int c=0;
  21.     if(b[N-1][N-1]!=0)return false;
  22.     for(int i=0;i<N;i++)
  23.     {
  24.         for(int j=0;j<N;j++)
  25.         {
  26.  
  27.             if(b[i][j]==k) 
  28.                 c++;
  29.  
  30.             k++;
  31.         }
  32.     }
  33.  
  34.     if(c==N*N-1)return true;
  35.     return false;
  36. }
  37. void findZero(int a[N][N])
  38. {
  39.     for(int i=0;i<N;i++)
  40.     {
  41.         for(int j=0;j<N;j++)
  42.         {
  43.            if(a[i][j] == 0){
  44.                X=i;Y=j;
  45.            }               
  46.         }
  47.     }
  48. }
  49. void solve(int a[N][N], string s)
  50. {
  51.      string x="";
  52. /*  for(int i=0;i<N;i++){
  53.      for(int j=0;j<N;j++)
  54.      cout<<a[i][j]<<" ";
  55.      cout<<endl;
  56.      }
  57.     system("pause");*/
  58.  
  59.     for(int i=0;i<N;i++)
  60.      for(int j=0;j<N;j++)
  61.        x=x+char(a[i][j]+'0');
  62.     int c[N][N];
  63.  
  64.  
  65.     if(chek(a)==1)
  66.     {
  67.     if(M=="")M=s;
  68.     if(s.length()<M.length())M=s;
  69.         cout << "Jol = " << s << endl;
  70.         system("pause");
  71.     }
  72.  
  73.     else if(map1[x]==0)
  74.     {
  75.          map1[x]=1;
  76.         findZero(a);
  77.         int l=s.length();
  78.         l--;
  79.         //i-1,j
  80.         if(X-1 >= 0){
  81.         for(int i1=0;i1<N;i1++)
  82.             for(int j1=0;j1<N;j1++)
  83.                 c[i1][j1] = a[i1][j1];
  84.         swap(c[X][Y],c[X-1][Y]);    
  85.  
  86. solve(c, s+char(c[X][Y]+'0'));
  87.         }
  88.         findZero(a);
  89.         x="";
  90.           //i+1,j
  91.         if(X+1 < N && s[l]!=char(a[X+1][Y]+'0')){
  92.         for(int i1=0;i1<N;i1++)
  93.             for(int j1=0;j1<N;j1++)
  94.                 c[i1][j1] = a[i1][j1];
  95.         swap(c[X][Y],c[X+1][Y]);      
  96.  
  97. solve(c, s+char(c[X][Y]+'0'));
  98.         }
  99.           //i,j-1
  100.          findZero(a); 
  101.          x="";
  102.         if(Y-1 >= 0 && s[l]!=char(a[X][Y-1]+'0')){
  103.         for(int i1=0;i1<N;i1++)
  104.             for(int j1=0;j1<N;j1++)
  105.                 c[i1][j1] = a[i1][j1];
  106.         swap(c[X][Y],c[X][Y-1]);        
  107.  
  108.        solve(c, s+char(c[X][Y]+'0'));     
  109.         }
  110.            //i,j+1
  111.         findZero(a);   
  112.         x="";
  113.         if(Y+1 < N && s[l]!=char(a[X][Y+1]+'0')){
  114.         for(int i1=0;i1<N;i1++)
  115.             for(int j1=0;j1<N;j1++)
  116.                 c[i1][j1] = a[i1][j1];
  117.         swap(c[X][Y],c[X][Y+1]);        
  118.  
  119.        solve(c, s+char(c[X][Y]+'0'));     
  120.         }
  121.  
  122.     }
  123.  
  124. }
  125.  
  126. int main()
  127. {
  128.     srand(time(0));
  129.     ifstream cin("input.txt");
  130.   /*  for(int i=0;i<N;i++)
  131.     {
  132.         for(int j=0; j<N;j++)
  133.         {
  134.             while(1)
  135.             {
  136.                 t = rand()%(N*N);
  137.                 if(b[t]==0)
  138.                     {
  139.                         
  140.                         b[t]=1;
  141.                         a[i][j] = t;
  142.                         break;
  143.                     }
  144.             }
  145.             cout << a[i][j] <<" ";
  146.         }
  147.         
  148.         cout << endl;
  149.     }*/
  150.  
  151.  
  152.       for(int i=0;i<N;i++)
  153.             for(int j=0; j<N;j++)
  154.              cin>>a[i][j];
  155.     cout<<"-----------------------\n";
  156.      for(int i=0;i<N;i++){
  157.      for(int j=0;j<N;j++)
  158.        cout<<a[i][j]<<" ";
  159.        cout<<endl;
  160.      }
  161.          cout<<"-----------------------\n";
  162.   /*   for(int i=1;;i++)
  163.       for(int j=0;j<answers.length();j++)
  164.        if(answers[j].length()==1){
  165.         cout<<answers[j]<<endl;
  166.             system("pause");
  167.         }*/
  168.     solve(a,"");
  169.     cout<<M<<endl;
  170.     system("pause");
  171.  
  172.  }
Success #stdin #stdout #stderr 0s 3436KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-----------------------
0 0 0 
0 0 0 
0 0 0 
-----------------------
stderr
copy 
sh: pause: not found
https://ideone.com/T6IpVD
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!