Telecommunications Rivalitati

Telecommunication-rivalitati.c

/*
test case 1:
4
0 0 0 1
0 0 1 0
0 1 0 0
1 0 0 0

test case 2:

4
0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0

Explicatie:
compania 1 este rivala cu companiile 2 si 4
compania 2 este rivala cu companiile 1 si 3
compania 3 este rivala cu companiile 2 si 4
compania 4 este rivala cu companiile 1 si 3

C1 -> C2 --> C1 -->C4 (nu este valida, c1 apare de 2 ori)

C1 -> C3 -> C2 -> C4

verificam 1 - 3 OK;
verificam 3 - 2 RIVAL , nu merge

circular, verificare rivalitati.

Problema 1: Breadth First Search

nodul de start = 4

4
adaugi intr-o coada toti descendentii sai: 4 0 2 5 1 3
*/
#include <stdio.h>
#define SIZE 100

int n;
int adj[SIZE][SIZE];//matricea de rivalitati
int arrangement[SIZE]; //aranjamentul la masa (inloc de culori)
int level, n;
int used[SIZE];//vector pentru a marca companiile folosite
int solution_count = 0; //numarul de solutii gasite
const int MAX_SOLUTIONS = 3;//limita pentru numarul de solutii


int sol() {

    return level == n;
}

void init() {
    arrangement[level] = 0;
}

int succ() {

    if(arrangement[level] < n) {
      arrangement[level]++;
      return 1;
    }
    return 0;
}

int valid() {

           int current_company = arrangement[level];

           //verifica daca compania nu este deja folosita
           if(used[arrangement[level]]) {
             return 0;
           }

           if(level == 1) {
              return 1;
           }
           //verificam rivalitatea cu vecinul din stanga
           int left_neighbor = arrangement[level-1];


           if(adj[current_company][left_neighbor] == 1) return 0;
           //pentru ultima pozitie verifica si rivalitatea cu primul (masa circulara)
           if(level == n) {
               int first_company = arrangement[1];
               if(adj[current_company][first_company]) return 0;
           }

           return 1;

}

void display_solution() {

      solution_count++;

      printf("Solutia %d: ", solution_count);

      for(int i = 1; i <= n; ++i) {
          printf("C%d", arrangement[i]);
          if(i < n) printf(" -> ");
      }

      printf(" -> C%d", arrangement[1]);

}

void backtracking() {

   int s, v;

   level = 1;

   while(level > 0 && solution_count < MAX_SOLUTIONS) {

         s = 1;
         v = 0;

         while(s && !v) {
             s = succ();
             if(s){
               v = valid();
             }
         }

         if(s) {

              //marcam compania ca fiind folosita
              used[arrangement[level]] = 1;
              if(sol()) {
                display_solution();
                //demarcheaza compania pentru urmatoarea incercare
                used[arrangement[level]] = 0;
                level--;
              } else {
                level++;
                init();
              }
         } else {
           if(level>0){
             used[arrangement[level]] = 0;
           }
           level--;
         }
   }

}

int main(int argc, char const *argv[]) {

  freopen("rivalitati.txt", "r", stdin);

  scanf("%d", &n);
  printf("Numarul de companii: %d\n", n);

  printf("Matricea de rivalitati: \n");

  for(int i = 1; i <= n; ++i) {
      for(int j = 1; j <= n; ++j) {
        scanf("%d", &adj[i][j]);
        printf("%d ", adj[i][j]);
      }
      printf("\n");
  }

  for(int i = 0; i < n; ++i) used[i] = 0;//initializare vectorul used

  printf("Cautam aranjamente valide pentru masa rotunda...\n");

  backtracking();

  if(solution_count == 0) {
    printf("\nNu s-au gasit solutii valide!\n");
  } else {
    printf("\nS-au gasit %d solutii valide.\n", solution_count);
  }

  return 0;
}


/*

*/