Advertisement
Dani_info

pb sariturii calului var.2

Dec 10th, 2019
155
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<iostream>
  2. #include<conio.h>
  3. #include<iomanip>
  4.  
  5. using namespace std;
  6.  
  7. const int dl[9]={0,-2,-1,1,2,2,1,-1,-2};
  8. const int dc[9]={0,1,2,2,1,-1,-2,-2,-1};
  9.  
  10. struct patratel
  11. {
  12.    int l,c;
  13. }x[100];
  14.  
  15. int d[100],n, nrsol=0;
  16.  
  17. void init(int k){
  18.  d[k]=0;
  19. }
  20.  
  21. int existasuccesor(int k){
  22.  return d[k]<8;
  23. }
  24.  
  25. void valoriposibile(int k){
  26.  x[k].l=x[k-1].l+dl[d[k]];
  27.  x[k].c=x[k-1].c+dc[d[k]];
  28. }
  29.  
  30. int estevalid(int k){
  31.  if(x[k].l<1 || x[k].l>n || x[k].c<1 || x[k].c>n) return 0;
  32.  for(int i=1;i<k;i++)
  33.    if(x[i].l==x[k].l && x[i].c==x[k].c) return 0;
  34.  return 1;
  35. }
  36.  
  37. int solutie(int k){
  38.  return k==n*n;
  39. }
  40.  
  41. void tipar(){
  42. nrsol++;
  43. for(int i=1;i<=n;i++)
  44.     {
  45.     for(int j=1;j<=n;j++)
  46.        for(int k=1;k<=n*n;k++)
  47.         if(x[k].l==i && x[k].c==j)
  48.          cout<<setw(2)<<k<<" ";
  49.     cout<<endl;
  50.     }
  51. cout<<endl<<endl;
  52. //getch();
  53. }
  54.  
  55. void back(){
  56.  x[1].l=1;x[1].c=1;
  57.  int k=2;
  58.  init(2);
  59.  while(k>1)
  60.    if(existasuccesor(k)) {
  61.     d[k]++;
  62.     valoriposibile(k);
  63.     if(estevalid(k))
  64.       if(solutie(k)) tipar();
  65.       else
  66.         {
  67.           k++;
  68.           init(k);
  69.         }
  70.    }
  71.    else k--;
  72.  }
  73.  
  74.  int main()
  75.  {
  76.     cout<<"n=";cin>>n;
  77.     back();
  78.     cout<<"Sunt "<<nrsol<<" solutii.";
  79.     return 0;
  80.  }
Advertisement
RAW Paste Data Copied
Advertisement