# PBinfo #4524 – Acces3 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

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.

## Cod sursă C++

```cpp
#include <fstream>
using namespace std;
ifstream fin("acces3.in");
ofstream fout("acces3.out");
int n,m,A[11][11],ip,jp,nrsol,kmax,B[11][11];
int di[]={-1,0,1,0};
int dj[]={0,1,0,-1};
int valid(int i, int j)
{
    if(i<1 || i>n || j<1 || j>m) return 0;
    if(A[i][j]!=0) return 0;
    return 1;
}
void back(int i, int j, int k)
{
    A[i][j]=k;
    if((i==1 && j==1) || (i==1 && j==m))
    {
        nrsol++;
        if(k>kmax)
            kmax=k;
    }
    for(int d=0;d<4;d++)
    {
        int iv=i+di[d], jv=j+dj[d];
        if(valid(iv,jv)) back(iv,jv,k+1);
    }
    A[i][j]=0;
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            char c;
            fin>>c;
            if(c=='#') A[i][j]=1;
            if(c=='P') { ip=i; jp=j; }
        }
    back(ip,jp,1);
    fout<<nrsol<<" "<<kmax;
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4524)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4524/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4524/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)