L'Edgar, l'Anna i la Brimo P58305

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.