107 lines
2.8 KiB
C
107 lines
2.8 KiB
C
// Laboratorio 4 - Esercizio 3 - main.c
|
|
// Matteo Schiff - s295565
|
|
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <stdbool.h>
|
|
|
|
enum Pietra{zaffiro, rubino, topazio, smeraldo};
|
|
|
|
// Esploro il set di collane valide in modo ordinato, quando arrivo alla fine della collana ne controllo
|
|
// la lunghezza e aggiorno se necessario la soluzione
|
|
void esploraSoluzioni(int z, int r, int t, int s, int len, int * tmp, int * max, int * sol) {
|
|
int added = false;
|
|
if (z > 0 && (len == 0 || (tmp[len - 1] == zaffiro || tmp[len - 1] == topazio))) {
|
|
tmp[len] = zaffiro;
|
|
esploraSoluzioni(z-1,r,t,s,len +1,tmp,max,sol);
|
|
added = true;
|
|
}
|
|
|
|
if (s > 0 && (len == 0 || (tmp[len - 1] == smeraldo || tmp[len - 1] == rubino))) {
|
|
tmp[len] = smeraldo;
|
|
esploraSoluzioni(z,r,t,s-1,len +1,tmp,max,sol);
|
|
added = true;
|
|
}
|
|
|
|
if (r > 0 && (len == 0 || (tmp[len - 1] == zaffiro || tmp[len - 1] == topazio))) {
|
|
tmp[len] = rubino;
|
|
esploraSoluzioni(z,r-1,t,s,len +1,tmp,max,sol);
|
|
added = true;
|
|
}
|
|
|
|
if (t > 0 && (len == 0 || (tmp[len - 1] == smeraldo || tmp[len - 1] == rubino))) {
|
|
tmp[len] = topazio;
|
|
esploraSoluzioni(z,r,t-1,s,len +1,tmp,max,sol);
|
|
added = true;
|
|
}
|
|
|
|
// se non è possibile più aggiungere pietre, ho raggiunto la lunghezza massima ottenibile dal ramo
|
|
if (!added) {
|
|
if (len > *max) {
|
|
*max = len;
|
|
for (int i = 0; i < len; i++) {
|
|
sol[i] = tmp[i];
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
void solveCase(int z, int r, int t, int s) {
|
|
int maxL = z+r+t+s;
|
|
int max = 0;
|
|
// vettore su cui la funzione costruisce le collane
|
|
int * tmp = malloc(maxL * sizeof(int));
|
|
// vettore utilizzato per memorizzare la soluzione
|
|
int * sol = malloc(maxL * sizeof(int));
|
|
|
|
printf("zaffiri = %d, rubini = %d, topazi = %d, smeraldi = %d; numero pietre = %d\n", z,r,t,s,maxL);
|
|
|
|
esploraSoluzioni(z,r,t,s,0,tmp,&max,sol);
|
|
|
|
printf("Collana massima di lunghezza %d\n", max);
|
|
for(int i = 0; i < max; i++) {
|
|
switch (sol[i])
|
|
{
|
|
case zaffiro:
|
|
printf("z ");
|
|
break;
|
|
case rubino:
|
|
printf("r ");
|
|
break;
|
|
case smeraldo:
|
|
printf("s ");
|
|
break;
|
|
case topazio:
|
|
printf("t ");
|
|
break;
|
|
default:
|
|
break;
|
|
}
|
|
}
|
|
putc('\n', stdout);
|
|
fflush(stdout);
|
|
free(tmp);
|
|
free(sol);
|
|
}
|
|
|
|
int main() {
|
|
int z, r, t, s, N = 0;
|
|
|
|
FILE *fp;
|
|
|
|
if ((fp = fopen("easy_test_set.txt", "r")) == NULL)
|
|
{
|
|
puts("Impossibile aprire il file");
|
|
return 1;
|
|
}
|
|
|
|
fscanf(fp, "%d", &N);
|
|
|
|
for (int i = 0; i < N; i++) {
|
|
fscanf(fp, " %d %d %d %d", &z, &r, &t, &s);
|
|
printf("Test case %d\n", i+1);
|
|
solveCase(z,r,t,s);
|
|
}
|
|
|
|
fclose(fp);
|
|
} |