Un volt massa llarg P74958

El mapa de la sortida de la dele és una graella n × n. La casa s’indica amb una ‘C’, els camins amb un punt, el bosc espès per on no es pot passar amb una ‘B’, i la posició del Pifa, que ha marxat a fer un volt, amb una ‘P’.

Sabent que els companys del Pifa sortiran a buscar-lo des de la casa, que tarden un minut en passar de casella en casella, i que només es poden fer moviments horitzontals i verticals, quanta estona trigaran com a mínim fins a trobar-lo?

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb un natural n entre 2 i 1000, seguit d’n files amb n caràcters cadascuna segons s’ha explicat anteriorment. Podeu suposar que hi ha exactament una ‘C’ i una ‘P’, i que hi ha almenys un camí entre ambdues lletres.

Sortida

Per a cada mapa, escriviu el temps mínim per trobar el Pifa.