Created
June 14, 2025 17:17
-
-
Save thinkphp/09a05a8773f8045d1d6c480a24f2f7e8 to your computer and use it in GitHub Desktop.
Telecommunications Rivalitati
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
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; | |
} | |
/* | |
*/ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment