Un volt massa llarg P74958


Statement
 

pdf   zip

thehtml

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.

Public test cases
  • Input

    5
    ..C..
    BBBB.
    PBBB.
    .BBB.
    .....
    
    2
    ..
    CP
    
    6
    .BP..B
    .CBB..
    ...B..
    B.B..B
    B.BB..
    ......
    

    Output

    12
    1
    14
    
  • Information
    Author
    Edgar Moreno
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++