Advertisement
andreisophie

Problema Comis Voiajorul

Sep 19th, 2019
205
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.12 KB | None | 0 0
  1. #include <fstream>
  2.  
  3. using namespace std;
  4.  
  5. int st[100],n,a[100][100];
  6. ifstream f("comis.in");
  7. ofstream g("comis.out");
  8.  
  9. void citire()
  10. {
  11.     f>>n;
  12.     for (int i=1;i<=n;i++)
  13.         for (int j=1;j<=n;j++)
  14.         {
  15.             f>>a[i][j];
  16.         }
  17. }
  18.  
  19. bool succesor(int k)
  20. {
  21.    if(st[k]<n)
  22.    {
  23.        st[k]++;
  24.        return 1;
  25.    }
  26.    return 0;
  27. }
  28.  
  29. bool valid(int k)
  30. {
  31.     if (a[st[k]][st[k-1]]==0 && k>1)
  32.         return 0;
  33.     for (int i=1;i<k;i++)
  34.         if (st[k]==st[i])
  35.             return 0;
  36.     return 1;
  37. }
  38.  
  39. void tipar(int k)
  40. {
  41.     for (int i=1;i<=k;i++)
  42.         g<<st[i]<<" ";
  43.     g<<'\n';
  44. }
  45.  
  46. bool solutie (int k)
  47. {
  48.     if (k==n && a[st[k]][1])
  49.         return true;
  50.     return false;
  51. }
  52.  
  53. void bck()
  54. {
  55.     int k,ok;
  56.  
  57.     k=2;
  58.     st[1]=1;
  59.     st[k]=0;
  60.  
  61.     while (k>1)
  62.     {
  63.         ok=0;
  64.         while (ok==0 && succesor(k))
  65.             ok=valid(k);
  66.  
  67.         if (ok==1)
  68.             if (solutie(k))
  69.                 tipar(k);
  70.             else
  71.                 st[++k]=0;
  72.         else
  73.             k--;
  74.     }
  75. }
  76.  
  77. int main()
  78. {
  79.     citire();
  80.     bck();
  81.     return 0;
  82. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement