# PBinfo #3380 – Castel2 – Rezolvare C++

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

## Enunț

Cerința
Se consideră un castel de formă dreptunghiulară, alcătuit din n*m camere dispuse pe n linii și m coloane. Intrarea în castel este în camera de coordonate (1,1), ieșirea în camera de coordonate (n,m), iar unele camere sunt închise. Dintr-o cameră se poate trece în camerele învecinate pe linie sau pe coloană. Unele camere sunt ocupate de zmei gripați; fiecare zmeu transmite viruși gripali în camera sa și în camerele aflate în jurul său la distanță mai mică sau egală cu k.

Pentru a câștiga inima Ilenei Cosânzeana, Făt-Frumos trebuie să traverseze castelul. Deoarece nu se pricepe la informatică vă roagă pe voi să determinați care este lungimea minimă a unui traseu care traversează castelul, trece doar prin camere deschise și nu trece prin camere afectate de zmei.

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


- – reprezentând cameră deschisă în care nu se află zmeu
Z – reprezentând cameră deschisă în care se află zmeu
# – reprezentând cameră închisă

Date de ieșire
Fișierul de ieșire castel2.out va conține pe prima linie numărul L, reprezentând lungimea minimă determinată.

Restricții și precizări

1 ≤ n,m ≤ 1000
1 ≤ k ≤ 100
dacă nu există niciun traseu, se va afișa valoarea -1
pentru 40 de puncte, k=0
pentru alte 20 de puncte, k=1
lungimea traseului este egală cu numărul de camere conținute de acesta, inclusiv camera de intrare în castel și cea de ieșire
virușii nu pot intra în camerele închise

Exemplul 2
castel2.in

5 7 0
-#--#--
-----Z-
##---#-
---#---
-----#-
castel2.out

11
Explicație
Un traseu posibil este următorul:

1  #  -  -  #  -  - 
2  3  4  5  6  Z  - 
#  #  -  -  7  #  - 
-  -  -  #  8  9 10 
-  -  -  -  -  # 11
Exemplul 2
castel2.in

5 7 2
-#--#--
-----Z-
##---#-
---#---
-----#-
castel2.out

13
Explicație
Un traseu posibil este următorul:

1  #  -  -  #  -  -
2  3  4  -  -  Z  -
#  #  5  -  -  #  -
-  -  6  # 10 11 12
-  -  7  8  9  # 13

## Cod sursă C++

```cpp
#include <iostream>
#include <iomanip>
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("castel2.in");
ofstream fout("castel2.out");
const int DIM = 1000,
          di[]={1,-1,0,0},
          dj[]={0,0,1,-1};
int  n , m , k;
int A[DIM + 1][DIM + 1], B[DIM + 1][DIM + 1];
int main(){
    fin >> n >> m >> k;
    for(int i = 1 ; i <= n ; i ++)
        for(int j = 1; j <= m ; j ++)
        {
            char x;
            fin >> x;
            if(x == '-')
                A[i][j] = 0;
            if(x == '#')
                A[i][j] = -1;
            if(x == 'Z')
                A[i][j] = 1;
        }
    queue<pair<int,int>> Q;
    for(int i = 1 ; i <= n ; i ++)
        for(int j = 1 ; j <= m ; j ++)
            if(A[i][j] == 1)
                Q.push({i,j});
    while(!Q.empty())
    {
        int i = Q.front().first, j = Q.front().second;
        Q.pop();
        if(A[i][j] <= k)
            for(int p = 0 ; p < 4 ; p ++)
            {
                int x = i+di[p], y = j+dj[p];
                if(x > 0 && x <= n && y > 0 && y <= m && A[x][y] == 0)
                    A[x][y] = A[i][j] + 1, Q.push({x,y});
            }
    }
    Q.push({1,1});
    B[1][1]=1;
    while(!Q.empty())
    {
        int i = Q.front().first, j = Q.front().second;
        Q.pop();
        for(int p = 0 ; p < 4 ; p ++)
        {
            int x = i + di[p], y = j + dj[p];
            if(x > 0 && x <= n && y > 0 && y <= m && A[x][y] == 0 && B[x][y] == 0)
                B[x][y] = B[i][j] + 1, Q.push({x,y});
        }
    }
    if(B[n][m] == 0)
        B[n][m] = -1;
    fout << B[n][m];
    cout << B[n][m] << endl;
}
```

## Resurse

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