ciao
sto confrontando varie soluzioni per Super Mario 2, in quanto è un problema utile per provare tecniche di base. Ho una soluzione ricorsiva, in cui provo diverse tecniche per implementare le strutture dati del grafo. Una delle tecniche (ammetto che è strana) è usare liste di adiacenza allocate staticamente, ovvero dichiaro staticamente una matrice N x N e uso ogni riga per contenere la lista di adiacenza. La tecnica in se funziona bene con altre soluzioni. Invece nel codice seguente accadono le seguenti cose:
1)Se dichiaro la matrice con elementi di tipo unsigned il programma fallisce con Signal 11, secondo me perché supero il limite di memoria
2) Se uso una matrice di unsigned short il programma va in timeout. Questo è strano, dal punto di vista teorico la complessità dovrebbe essere la stessa del caso in cui uso delle normali liste di adiacenza dinamiche. Cosa può esserci che rallenta il codice? Forse l’uso di unsigned short rallenta?
Ecco il codice. mediante la define DATA_STRUCTURE, si può selezionare la struttura dati usata per memorizzare il grafo (spero non sia troppo incasinata da leggere per via della parametrizzazione)
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
/* #define DEBUG */
#define MAX_N 10000
#define MAX_M 100000
/* Le macro seguenti definiscono nomi per le strutture dati per memorizzare archi */
#define LISTA_ARCHI 0
#define MATRICE_ADIACENZA_STATICA 1
#define MATRICE_ADIACENZA_SEMI_DINAMICA 2
#define MATRICE_ADIACENZA_DINAMICA 3
#define LISTE_ADIACENZA_STATICHE 4
#define LISTE_ADIACENZA_DINAMICHE 5
/* La macro seguente seleziona la struttura dati per memorizzare gli archi: deve essere
posta uguale ad una delle macro che definiscono i nomi delle strutture dati */
#define DATA_STRUCTURE LISTE_ADIACENZA_STATICHE
/* tipo coppia */
struct pair {
unsigned first, second;
};
/* file handlers */
FILE *in, *out;
/* variabili globali:
S è il numero di monete raccolte, le altre hanno gli stessi significati del testo
*/
unsigned N, M, S;
/* insieme dei nodi raggiungibili da 0, implicitamente inizializzato a insieme vuoto */
bool raggiungibili[ MAX_N ];
/* insieme delle monete presenti nei nodi */
unsigned monete[ MAX_N ];
/*
Struttura dati usata dalla funzione calcola_cammini_minimi per memorizzare gli archi,
selezionabile mediante la macro DATA_STRUCTURE
Se DATA_STRUCTURE vale LISTA_ARCHI si usa la lista di archi globale, realizzata
mediante un array statico
Se DATA_STRUCTURE vale MATRICE_ADIACENZA_STATICA si usa una matrice di adiacenza
allocata staticamente
Se DATA_STRUCTURE vale MATRICE_ADIACENZA_SEMI_DINAMICA si usa una matrice di
adiacenza allocata in modo semi-dinamico: un array statico che contiene
puntatori alle righe e ciascuna riga e' allocata dinamicamente
Se DATA_STRUCTURE vale MATRICE_ADIACENZA_DINAMICA si usa una matrice di adiacenza
allocata in modo dinamico: un array dinamico che contiene puntatori alle righe
e ciascuna riga e' allocata dinamicamente
Se DATA_STRUCTURE vale LISTE_ADIACENZA_STATICHE si usano liste di adiacenza
allocate staticamente
Se DATA_STRUCTURE vale LISTE_ADIACENZA_DINAMICHE si usano liste di adiacenza
allocate dinamicamente
Altrimenti, il caso di default e' LISTA_ARCHI
*/
#if DATA_STRUCTURE == MATRICE_ADIACENZA_STATICA
bool archi[ MAX_N ][ MAX_N ];
#elif DATA_STRUCTURE == MATRICE_ADIACENZA_SEMI_DINAMICA
bool *archi[ MAX_N ];
#elif DATA_STRUCTURE == MATRICE_ADIACENZA_DINAMICA
bool **archi;
#elif DATA_STRUCTURE == LISTE_ADIACENZA_STATICHE
/* array che contiene le lunghezze delle liste di adiacenza */
unsigned numero_archi[ MAX_N ];
/* memoria allocata per le liste di adiacenza:
in questa versione devo usare unsigned short per non violare il limite di memoria */
unsigned short archi[ MAX_N ][ MAX_N ];
#elif DATA_STRUCTURE == LISTE_ADIACENZA_DINAMICHE
struct list_node {
unsigned node;
struct list_node *next;
};
/* array di puntatori a liste di adiacenza, ogni puntatore e' implicitamente inizializzato
a NULL */
struct list_node *archi[ MAX_N ];
#else
struct pair lista_archi[ MAX_M ];
#endif
/*
Questa funzione legge la lista degli archi da input e costruisce la rappresentazione
in memoria centrale dell'insieme degli archi
*/
#if DATA_STRUCTURE == MATRICE_ADIACENZA_STATICA ||\
DATA_STRUCTURE == MATRICE_ADIACENZA_SEMI_DINAMICA ||\
DATA_STRUCTURE == MATRICE_ADIACENZA_DINAMICA
void leggi_archi( void ) {
/* se si usa MATRICE_ADIACENZA_SEMI_DINAMICA o MATRICE_ADIACENZA_DINAMICA alloca
dinamicamente le righe inizializzando gli elementi a false
inoltre se si usa MATRICE_ADIACENZA_DINAMICA alloca anche l'array che contiene
i puntatori alle righe */
#if DATA_STRUCTURE == MATRICE_ADIACENZA_DINAMICA
archi = malloc( N * sizeof( bool * ) );
#endif
#if DATA_STRUCTURE == MATRICE_ADIACENZA_SEMI_DINAMICA ||\
DATA_STRUCTURE == MATRICE_ADIACENZA_DINAMICA
for ( unsigned i = 0 ; i < N ; i++ )
archi[ i ] = calloc( N, sizeof( bool ) );
#endif
/* memorizza archi */
for ( unsigned i = 0, u, w ; i < M ; i++ ) {
fscanf( in, "%u%u", &u, &w );
archi[ u ][ w ] = archi[ w ][ u ] = true;
}
}
#elif DATA_STRUCTURE == LISTE_ADIACENZA_STATICHE
void leggi_archi( void ) {
/* memorizza archi */
for ( unsigned short i = 0, u, w ; i < M ; i++ ) {
fscanf( in, "%hu%hu", &u, &w );
archi[ u ][ numero_archi[ u ]++ ] = w;
archi[ w ][ numero_archi[ w ]++ ] = u;
}
}
#elif DATA_STRUCTURE == LISTE_ADIACENZA_DINAMICHE
void leggi_archi( void ) {
/* memorizza archi */
for ( unsigned i = 0, u, w ; i < M ; i++ ) {
fscanf( in, "%u%u", &u, &w );
struct list_node *p = malloc( sizeof( struct list_node ) );
p -> node = w;
p -> next = archi[ u ];
archi[ u ] = p;
p = malloc( sizeof( struct list_node ) );
p -> node = u;
p -> next = archi[ w ];
archi[ w ] = p;
}
}
#else
void leggi_archi( void ) {
/* memorizza archi */
for ( unsigned i = 0, u, w ; i < M ; i++ ) {
fscanf( in, "%u%u", &u, &w );
lista_archi[ i ].first = u;
lista_archi[ i ].second = w;
}
}
#endif
/*
Questa funzione visita in profondità il grafo, in modo ricorsivo
Inoltre memorizza in S il numero di monete raggiungibili a partire dal nodo iniziale
*/
#if DATA_STRUCTURE == MATRICE_ADIACENZA_STATICA ||\
DATA_STRUCTURE == MATRICE_ADIACENZA_SEMI_DINAMICA ||\
DATA_STRUCTURE == MATRICE_ADIACENZA_DINAMICA
void visita( unsigned v ) {
/* imposta v a visitato e incrementa contatore di monete raccolte */
raggiungibili[ v ] = true, S += monete[ v ];
/* visita ricorsivamente i nodi adiacenti */
for ( unsigned i = 0 ; i < N ; i++ )
if ( archi[ v ][ i ] && !raggiungibili[ i ] ) visita( i );
}
#elif DATA_STRUCTURE == LISTE_ADIACENZA_STATICHE
void visita( unsigned v ) {
/* imposta v a visitato e incrementa contatore di monete raccolte */
raggiungibili[ v ] = true, S += monete[ v ];
/* visita ricorsivamente i nodi adiacenti */
for ( unsigned i = 0 ; i < numero_archi[ v ] ; i++ )
if ( !raggiungibili[ archi[ v ][ i ] ] ) visita( archi[ v ][ i ] );
}
#elif DATA_STRUCTURE == LISTE_ADIACENZA_DINAMICHE
void visita( unsigned v ) {
/* imposta v a visitato e incrementa contatore di monete raccolte */
raggiungibili[ v ] = true, S += monete[ v ];
/* visita ricorsivamente i nodi adiacenti */
for ( struct list_node *p = archi[ v ] ; p ; p = p -> next )
if ( !raggiungibili[ p -> node ] ) visita( p -> node );
}
#else
void visita( unsigned v ) {
/* imposta v a visitato e incrementa contatore di monete raccolte */
raggiungibili[ v ] = true, S += monete[ v ];
/* visita ricorsivamente i nodi adiacenti */
for ( unsigned i = 0 ; i < M ; i++ )
if ( lista_archi[ i ].first == v && !raggiungibili[ lista_archi[ i ].second ] )
visita( lista_archi[ i ].second );
else if ( lista_archi[ i ].second == v && !raggiungibili[ lista_archi[ i ].first ] )
visita( lista_archi[ i ].first );
}
#endif
int main( void ) {
in = fopen( "input.txt", "r" );
/* leggi prima riga input */
fscanf( in, "%u%u", &N, &M );
/* leggi monete */
for ( unsigned i = 0 ; i < N ; i++ ) fscanf( in, "%u", &monete[ i ] );
/* legge e memorizza grafo */
leggi_archi();
fclose( in );
/* calcola raggiungibili a partire da 0 */
visita( 0 );
/* scrivi output */
out = fopen( "output.txt", "w" );
fprintf( out, "%u\n", S );
fclose( out );
return 0;
}
) la sola matrice occupa 400MB; quindi ogni altra considerazione è priva di significato, visto che già la matrice da sola fa superare il limite globale di memoria.