#include#include #define N_MAX 100 #define INNOCUO 0 #define PERICOLO -1 int labirinto[N_MAX+2][N_MAX+2]; // labirinto con cornice... int MOSSE[8][2]= // gli 8 lastroni adiacenti { {-1, -1}, { 0, -1}, {+1, -1}, {-1, 0}, {+1, 0}, {-1, +1}, { 0, +1}, {+1, +1} }; //+++++++++++++++++++++++++++++++++ ADT CODA ++++++++++++++++++++++++++++++ struct nodo { int riga, colonna; nodo *link; }; typedef struct nodo *pnodo; void accoda(pnodo &, pnodo &, int , int ); void servi (pnodo &, pnodo &, int &, int &); //+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ //+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ int main() { int N; // dimensione del labirinto char buffer[N_MAX+1]; // riga input FILE *file; file = fopen("input.txt", "r"); fscanf(file, "%d", &N); for(int i=1; i <= N; i++) { fscanf(file, "%s", buffer); for(int j=0; j < N_MAX; j++) { if(buffer[j]=='*') labirinto[i][j+1]=INNOCUO; else if(buffer[j]=='+') labirinto[i][j+1]=PERICOLO; } } fclose(file); for(int i=0; i <= N+1; i++) // aggiunge cornice di pericoli... { labirinto[0 ][i ]=PERICOLO; labirinto[N+1][i ]=PERICOLO; labirinto[i ][0 ]=PERICOLO; labirinto[i ][N+1]=PERICOLO; } //++++++++++++++++++++++++++++++++++++ visita tutte le lastre +++++++++ pnodo testa=NULL; pnodo coda =NULL; labirinto[1][1]=1; // ingresso ha distanza 1 accoda(testa, coda, 1, 1); // (1, 1) è da visitare int lastra, x, nx, y, ny; while(testa != NULL) { servi(testa, coda, x, y); lastra=labirinto[x][y]; for(int i=0; i < 8; i++) { nx=x+MOSSE[i][0]; ny=y+MOSSE[i][1]; if(labirinto[nx][ny] == INNOCUO || // se (nx, ny) è da visitare labirinto[nx][ny] > lastra ) // già visitato ma peggio... { labirinto[nx][ny]=lastra+1; // distanza accoda(testa, coda, nx, ny); // ricordati di visitare... } } } //+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ int risposta=labirinto[N][N]; //+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ file = fopen("output.txt", "w"); fprintf(file, "%d", risposta); fclose(file); return 0; } //+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ //+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ void accoda(pnodo &t, pnodo &c, int x, int y) { pnodo p=(pnodo)malloc(sizeof(struct nodo)); p->riga =x; p->colonna=y; p->link =NULL; if(t == NULL) t=p; else c->link=p; c=p; } void servi(pnodo &t, pnodo &c, int &x, int &y) { x=t->riga; y=t->colonna; pnodo p=t; t=t->link; free(p); }