Olimpiadi di Informatica - Selezione Regionale 2008
problema
Mappa antica (MAPPA)
- livello difficoltà 2
soluzione in C++ proposta dal prof.Carlo Salvagno
/* Selezione Regionale 2008 - Mappa antica (MAPPA) - Difficoltà D = 2 Descrizione del problema: Topolino è in missione per accompagnare una spedizione archeologica che segue un'antica mappa acquisita di recente dal museo di Topolinia. Raggiunta la località dove dovrebbe trovarsi un prezioso e raro reperto archeologico, Topolino si imbatte in un labirinto che ha la forma di una gigantesca scacchiera quadrata di NxN lastroni di marmo. Nella mappa, sia le righe che le colonne del labirinto sono numerate da 1 a N. Il lastrone che si trova nella posizione corrispondente alla riga "r" e alla colonna "c" viene identificato mediante la coppia di interi (r, c). I lastroni segnalati da una crocetta '+' sulla mappa contengono un trabocchetto mortale e sono quindi da evitare, mentre i rimanenti sono innocui e segnalati da un asterisco '*'. Topolino deve partire dal lastrone in posizione (1, 1) e raggiungere il lastrone in posizione (N, N), entrambi innocui. Può passare da un lastrone a un altro soltanto se questi condividono un lato o uno spigolo (quindi può procedere in direzione orizzontale, verticale o diagonale ma non saltare) e, ovviamente, questi lastroni devono essere innocui. Tuttavia, le insidie non sono finite qui: per poter attraversare incolume il labirinto Topolino deve calpestare il minor numero possibile di lastroni innocui (e ovviamente nessun lastrone con trabocchetto). Aiutate Topolino a calcolare tale numero minimo. Dati di input: Il file "input.txt" è composto da N+1 righe. La prima riga contiene un intero positivo che rappresenta la dimensione N di un lato del labirinto a scacchiera. Le successive N righe rappresentano il labirinto a scacchiera: la r-esima di tali righe contiene una sequenza di N caratteri '+' oppure '*', dove '+' indica un lastrone con trabocchetto mentre '*' indica un lastrone sicuro. Tale riga rappresenta i lastroni che stanno sulla r-esima riga della scacchiera: di conseguenza, il c-esimo carattere corrisponde al lastrone in posizioe (r, c). Dati di output: Il file "output.txt" è composto da una sola riga contenente un intero che rappresenta il minimo numero di lastroni innocui (ossia indicati con '*') che Topolino deve attraversare a partire dal lastrone in posizione (1, 1) per arrivare incolume al lastrone in posizione (N, N). Notare che i lastroni (1, 1) e (N, N) vanno inclusi nel conteggio dei lastroni attraversati. Assunzioni: - 1 <= N <= 100; - 1 <= r,c <= N; - E' sempre possibile attraversare il labirinto dal lastrone in posizione (1, 1) al lastrone in posizione (N, N); inoltre tali due lastroni sono innocui. Esempi di input/output: +-----------+------------+ | input.txt | output.txt | +-----------+------------+ | 4 | 5 | | *+++ | | | +**+ | | | +*+* | | | +*** | | +-----------+------------+ Nota: Un programma che restituisce sempre lo stesso valore, indipendentemente dai dati in "input.txt", non totalizza alcun punteggio. -------------------------------------------------------------------------------- Olimpiadi di Informatica - Selezione Regionale 2008 Soluzione problema MAPPA ANTICA proposta da Carlo Salvagno, Referente Regionale VEN1 - ITIS "C.Zuccante", in Dev-C++ IDEA RISOLUTIVA La mappa viene rappresentata con una matrice (mappa) di interi di ordine n+2, ossia si utilizza un bordo sentinella intorno alla matrice originale in modo da garantire che ogni cella interna sia attorniata sempre da 8 celle. Il valore di una cella va così interpretato: - se nullo, si tratta di un "trabocchetto" e quindi non va attraversato; - se > 0, è il numero ottimo di lastroni attraversati da (1,1) per raggiungerlo. Durante la lettura da file le celle della mappa vengono poste a zero per le celle "+" (trabocchetto) e ad un valore "infinito" (basta anche n*n) per le celle "*" (sicure). La cella (1,1) viene inizializzata ad 1 e a partire da questa si visita la matrice per righe con una strategia tipica della programmazione dinamica. Per ogni cella di posizione (r, c) che non sia un trabocchetto si analizzano le celle raggiungibili. Per ogni cella raggiungibile si esegue l'aggiornamento: mappa[r-ragg, c-ragg] := MIN( mappa[r, c] +1, mappa[r-ragg, c-ragg] Si osservi che le celle trabocchetto restano a zero. Il risultato è il valore finale memorizzato in mappa[n, n]. Si osservi che il contenuto iniziale delle celle sul bordo non influisce sul risultato. La complessità dell'algoritmo è quadratica. ------------------------------------------------------------------------------*/ #include <iostream.h> #include <fstream.h> #include <stdlib.h> int main(int argc, char *argv[]) { ifstream in("input.txt"); ofstream out("output.txt"); const int NMAX = 102; const int INFINITO = 10000; const int TRAB = 0; int mappa[NMAX][NMAX]; int n; char riga[NMAX]; in >> n; in.getline(riga, NMAX); // lettura delle righe for (int r =1; r <= n; r++ ) { in.getline(riga, n+1); for (int c=0; c<n; c++) if (riga[c] == '*') mappa[r][c+1] = INFINITO; else mappa[r][c+1] = TRAB; } mappa[1][1] = 1; for (int r=1; r<=n; r++) for (int c=1; c <=n; c++) { if (mappa[r][c]){ /* se non trabocchetto */ int h = mappa[r][c] + 1; /* -- stessa riga a sx -- */ if (mappa[r][c-1] > h ) mappa[r][c-1] = h; /* -- stessa riga a dx -- */ if (mappa[r][c+1] > h) mappa[r][c+1] = h; /* -- riga prec. -- */ for (int ic=c-1; ic<=c+1; ic++) { if (mappa[r-1][ic] > h) mappa[r-1][ic] = h; } /* -- riga succ. -- */ for (int ic=c-1; ic<=c+1; ic++) { if (mappa[r+1][ic] > h) mappa[r+1][ic] = h; } } } out << mappa[n][n] <<"\n"; out.close(); in.close(); return 0; }
Testo del problema