Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
#include <stdio.h>
#ifdef DEBUGGING
#define WHERESTR "[file %s, line %d]: "
#define WHEREARG __FILE__, __LINE__
#define DEBUGPRINT2(...) fprintf(stderr, __VA_ARGS__)
#define DEBUGPRINT(_fmt, ...) DEBUGPRINT2(WHERESTR _fmt, WHEREARG, __VA_ARGS__)
#else
#define DEBUGPRINT(_tmt, ...) /** nothing */
#endif
int distanza(int, int, int, int);
int idCitta(int);
int main()
{
int i;
int x[100];
int y[100];
int citta[100];
int cittaVisitate[100];
int cittaIniziale;
int cittaCorrente;
int cittaSuccessiva;
int numeroDiCitta;
int numeroDiCittaVisitate;
int distanzaMinima;
int distanzaPercorsa = 0;
for (int i = 0; i < 100; i++) {
cittaVisitate[i] = 0;
citta[i] = -1;
}
do {
printf("Quante citta vuoi inserire? (%d-%d): ", 1, 100);
scanf("%d", &numeroDiCitta);
printf("\n");
} while (numeroDiCitta < 1 || numeroDiCitta > 100);
for (i = 0; i < numeroDiCitta; i++) {
printf("Inserisci coordinate della citta %d\n", 1 + i);
citta[i] = 1 + i;
printf("\t coordinata x: ");
scanf("%d", &x[i]);
printf("\t coordinata y: ");
scanf("%d", &y[i]);
}
do {
printf("Inserisci l'id della citta da cui vuoi iniziare il tuo fantastico viaggio: ");
scanf("%d", &cittaIniziale);
} while (cittaIniziale < 1 || cittaIniziale > 100);
cittaCorrente = cittaIniziale - 1;
numeroDiCittaVisitate = 0;
do {
DEBUGPRINT("Visiting city %d\n", idCitta(cittaCorrente));
// Citta <cittaCorrente> non ancora visitata
if (!cittaVisitate[cittaCorrente]) {
DEBUGPRINT("Finding nearest cities\n", "");
distanzaMinima = -1;
// Calcolo delle citta piu vicine a <cittaCorrente>
for (i = 0; i < numeroDiCitta; i++) {
if (cittaVisitate[i]) {
DEBUGPRINT("Skipping distance calculation of visited cities\n", "");
} else {
// Evitiamo di calcolare la distanza di <cittaCorrente> con se stessa
if (cittaCorrente == i) {
DEBUGPRINT("Skipping distance calculation from %d to itself\n", idCitta(cittaCorrente));
} else {
// Se la distanza minima è < 0 o minore della precendente distanza Minima...
if (distanzaMinima > distanza(x[cittaCorrente], y[cittaCorrente], x[i], y[i]) || distanzaMinima < 0) {
distanzaMinima = distanza(x[cittaCorrente], y[cittaCorrente], x[i], y[i]);
DEBUGPRINT("Candidate next city %d. Distance (%d, %d) is %d\n", idCitta(i), idCitta(cittaCorrente), idCitta(i), distanzaMinima);
cittaSuccessiva = i;
}
}
}
}
if ((cittaSuccessiva >= 0 && cittaSuccessiva <= numeroDiCitta) && citta[cittaSuccessiva] > 0) {
DEBUGPRINT("Passed city %d from candidate to effective next city to visit\n", idCitta(cittaSuccessiva));
DEBUGPRINT("Marking city %d as visited\n", idCitta(cittaCorrente));
// Distanza percorsa
distanzaPercorsa += distanzaMinima;
// Stampiamo il percorso
printf("Passare da City %d\n", idCitta(cittaCorrente));
// Segniamo <cittaCorrente> come visitata
cittaVisitate[cittaCorrente] = 1;
// Mettiamo <cittaSuccessiva> in <cittaCorrente> così che nella prossiam iterazione
// venga visitata la nuova città
cittaCorrente = cittaSuccessiva;
}
} else {
DEBUGPRINT("Skipping, already visited city %d\n", idCitta(cittaCorrente));
}
numeroDiCittaVisitate++;
} while(numeroDiCittaVisitate < numeroDiCitta);
printf("Distaza percorsa: %d\n", distanzaPercorsa);
}
int distanza(int x1, int y1, int x2, int y2)
{
return ((x2 - x1) * (x2 - x1)) + ((y2 - y1) * (y2 - y1));
}
int idCitta(int citta)
{
return 1 + citta;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.