/* Olimpiadi di Informatica - Regionali 2008
 Soluzione per problema: MAPPA - 
proposta da:  Carlo Salvagno 2008 - Referente Regionale VEN1 - ITIS  "C. Zuccante"

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 positivo, indica 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]

(Su segnalazione della prof.ssa Paola Masin dell'ITIS. Marconi di Verona che ha corretto 
l'errore della mia precedente soluzione: si deve memorizzare in una coda le coordinate delle celle
modificate; l'elaborazione continua finchè la coda non è vuota).

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>
#include <fstream>
#include <string>
using namespace std;
/* ------------------------------------------------------------------------- */
int main(int argc, char *argv[]) {
  ifstream in("input.txt");
  ofstream out("output.txt");
  const int NMAX = 102;
  const int INFINITO = 10000;
  const int DIM_CODA = 10000;
  const int TRAB = 0;
  int mappa[NMAX][NMAX];
  int coda[DIM_CODA][2]; 
  int n, j, i, r, c, h;
  char riga[NMAX];
  int indTesta=0, indCoda=1;

  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;
  //accodo le coordinate del primo lastrone
  coda[0][0] = 1;
  coda[0][1] = 1;
  while (indTesta != indCoda ) { //la coda NON è vuota
     //estrazione dalla coda dell'elemento di testa
     r= coda[indTesta][0];
     c= coda[indTesta][1];
     indTesta = (indTesta + 1) % DIM_CODA;
     h = mappa[r][c] + 1;
     for ( i=r-1; i<=r+1; i++) { 
       for ( j=c-1; j<=c+1; j++) {
         if ((mappa[i][j]) && (mappa[i][j] > h )) {
                              mappa[i][j] = h;
                              //accoda le coordinate del lastrone di cui è stata 
                              // aggiornata la distanza
                              coda[indCoda][0]=i;
                              coda[indCoda][1]=j;
                              indCoda = (indCoda + 1) % DIM_CODA;
         }//if
       }//for-j
     }//for-i
   } //while
 
  out << mappa[n][n] <<"\n";
//  cout << mappa[n][n];
//  cin >>n;
  out.close();
  in.close();
  return 0;
}