Rezolvare PBinfo #4524

Cerința

Se consideră o clădire de formă dreptunghiulară, împărțită în n*m camere, dispuse sub forma unei matrice cu n linii și m coloane. Dintr-o cameră se poate trece în oricare dintre cele 4 camere vecine pe linie sau pe coloană. Unele camere sunt închise, și în ele nu se poate intra deloc. Trecerea dintr-o cameră în altă cameră durează un minut.

Accesul în clădire se realizează prin una dintre camerele de pe linia 1 și coloana 1 sau linia 1 și coloana m. Ieșirea din clădire durează un minut.

În una dintre camere se află proprietarul clădirii, care dorește să afle care este numărul de variante în care poate să părăsească clădirea și care este durata maximă exprimată în minute a unui traseu de ieșire fără ca să treacă de două ori prin aceeași cameră.

Date de intrare

Fișierul de intrare acces3.in conține pe prima linie numerele n m; următoarele n linii conțin câte m caractere, care pot fi:

• - – reprezintă o cameră liberă
• # – reprezintă o cameră închisă
• P – reprezintă camera proprietarului, care se consideră liberă

Date de ieșire

Fișierul de ieșire acces3.out va conține numere a și b separate printr-un spațiu. Numărul a reprezintă numărul de moduri în care poate proprietarul să părăsească clădirea, iar b reprezintă durata maximă a unui traseu de ieșire, exprimată în minute.

Restricții și precizări

• 1 ≤ n, m ≤ 10
• Se garantează faptul că proprietarul poate părăsi clădirea.

Exemplu:

acces3.in

4 6
--#-#-
--##--
--P---
-----#

acces3.out

54 16 

Explicație

Un traseu de durată maximă cu afișarea pașilor minut cu minut este următorul:

4 3 #  -  # 15
5 2 #  #  - 14
6 1 P  - 12 13
7 8 9 10 11 #

Ieșirea prin camera (1,6) durează un minut, de aceea timpul maxim este 16.