L'Edgar, l'Anna i la Brimo P58305


Statement
 

pdf   zip

thehtml

L’Edgar, l’Anna i la seva amiga Brigit Motlló (àlies la Brimo) s’estimen molt. Tant, que sovint queden a la nit als carrers de Barcelona, al caliu del foc de la seva passió. Malauradament, sempre es troben amb un mateix problema, i és que la Brigit té un nas molt fi, i és incapaç de passar per carrers on hi ha contenidors. Ajudeu-los a saber si aquesta nit la Brigit podrà arribar fins al punt on han quedat tots tres.

Considerarem que Barcelona és una quadrícula amb n files i m columnes, on un es pot moure d’una cel·la a qualsevol de les (com a molt) quatre adjacents. A algunes cel·les hi ha contenidors, de manera que no hi pot passar la Brigit. Determineu si existeix algun camí des d’on es troba la Brigit fins al punt on han quedat sense passar per contenidors.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb n i m, ambdues entre 1 i ‍300, seguides d’n files amb m caràcters cadascuna. Els punts indiquen cel·les lliures, i les ‘C’ contenidors. Hi ha exactament una ‘B’ indicant la cel·la on es troba la Brigit, i una ‘Q’ indicant la cel·la on han quedat.

Sortida

Per a cada cas, escriviu “aquesta nit hi haura passio” si la Brigit els podrà trobar, i “aquesta nit hi haura pau” en cas contrari.

Public test cases
  • Input

    3 3
    B..
    CC.
    CCQ
    
    2 5
    .BC.Q
    ...C.
    
    4 3
    .Q.
    CCC
    CBC
    CCC
    

    Output

    aquesta nit hi haura passio
    aquesta nit hi haura pau
    aquesta nit hi haura pau
    
  • Information
    Author
    Miquel Ortega
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++