daily pastebin goal
20%
SHARE
TWEET

Untitled

a guest Dec 7th, 2017 52 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstdio>
  2. #include <vector>
  3. #include <cstdlib>
  4. using namespace std;
  5.  
  6. FILE *in;
  7. bool Finished;
  8.  
  9. struct Queen {
  10.     int var;
  11.     vector<int> domen;
  12.     vector<bool> visited;
  13.     };
  14.  
  15. void ForwardCheck(vector<struct Queen> &Q, int index, int N)
  16. {
  17.     for(int i=index+1; i<N; i++) {
  18.             Q[i].visited[ Q[index].var ] = true;
  19.  
  20.             if( Q[index].var + (i-index) < N )
  21.                 Q[i].visited[ Q[index].var + (i-index) ] = true;
  22.  
  23.             if( Q[index].var - (i-index) > 0 )
  24.                 Q[i].visited[ Q[index].var - (i-index) ] = true;
  25.             }
  26.  
  27. // Pratim vrijednosti - "manual" debug
  28.    system("cls");
  29.     for(int i=1; i<N; i++) {
  30.         printf("Q%d\n", i);
  31.         printf("VAR: %d\n", Q[i].var);
  32.         printf("DOMEN: ");
  33.         for(int k=1; k<N; k++)
  34.             printf("%d ", k);
  35.         printf("\n");
  36.         printf("VISITED: ");
  37.         for(int k=1; k<N; k++) {
  38.             if(Q[i].visited[k] == true)
  39.                 printf("T");
  40.             else printf("F");
  41.             }
  42.         printf("\n\n");
  43.         }
  44.  
  45. }
  46.  
  47. int CSP(vector<struct Queen> Q, int index, int N)
  48. {
  49.     if(index == N) {
  50.         Finished = true;
  51.         for(int i=1; i<N; i++)
  52.             printf("%d ", Q[i].var);
  53.         }
  54.  
  55.     else
  56.         while( !Finished )
  57.         {
  58.             int VAR;
  59.             bool found = false;
  60.             for(int i=1; i<N; i++) {
  61.                 if(Q[index].visited[i] == false) {
  62.                     VAR = Q[index].domen[i];
  63.                     Q[index].visited[i] = true;
  64.                     found = true;
  65.                     break;
  66.                     }
  67.                 }
  68.  
  69.             if(found == false) return 0;
  70.  
  71.             Q[index].var = VAR;
  72.             ForwardCheck(Q, index, N);
  73.             CSP(Q, index+1, N);
  74.         }
  75.  
  76.     return 0;
  77. }
  78.  
  79. int main()
  80. {
  81.     in = fopen("test.in", "r");
  82.  
  83.     int N;
  84.     Finished = false;
  85.     fscanf(in, "%d", &N);
  86.  
  87.     N = N+1; // Zbog indexiranja, da pocne od 1 do N-1
  88.     vector<struct Queen> Q;
  89.    
  90.     // Init
  91.     for(int i=0; i<N; i++) {
  92.         Queen newQueen;
  93.  
  94.         for(int k=0; k<N; k++) {
  95.             newQueen.domen.push_back( k );
  96.             bool newBool = false;
  97.             newQueen.visited.push_back( newBool );
  98.             }
  99.         Q.push_back( newQueen );
  100.         }
  101.    
  102.     CSP(Q, 1, N);
  103.  
  104.     fclose(in);
  105.     return 0;
  106. }
RAW Paste Data
Top