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

#include <bits/stdc++.h>

using namespace std;
#define inf 9999
ifstream cin("castel2.in");
ofstream cout("castel2.out");

const int di[] = { 0 , 0 , -1 , 1};
const int dj[] = {-1 , 1 ,  0 , 0};

int n , m , k , a[1001][1001] , b[1001][1001];
char c;
struct poz
{
    int i , j;
    poz(int i_, int j_)
    {
        i = i_;
        j = j_;
    }
    poz(){};
};
queue <poz> Q;

bool inside(int i , int j)
{
    return i >= 1 && i <= n && j >= 1 && j <= m;
}

void lee(int i , int j)
{
    poz x;
    x.i = i;
    x.j = j;
    Q.push(x);
    b[x.i][x.j] = 1;
    while(!Q.empty())
    {
        poz r;
        r = Q.front();
        for(int d = 0 ; d < 4 ; d++)
        {
            int inou = r.i + di[d];
            int jnou = r.j + dj[d];
            if(inside(inou , jnou) && b[inou][jnou] == 0 && a[inou][jnou] != -1 && a[inou][jnou] != -2)
            {
                Q.push({inou , jnou});
                b[inou][jnou] = b[r.i][r.j] + 1;
            }
        }
        Q.pop();
    }
}

int main()
{
    cin >> n >> m >> k;
    for(int i = 1 ; i <= n ; i++)
    {
        for(int j = 1 ; j <= m ; j++)
        {
            cin >> c;
            if(c == '#') a[i][j] = -1;
            if(c == 'Z') a[i][j] = -2;
        }
    }

    queue< pair<poz, int> > Q;

    for (int i = 1; i <= n; ++ i)
        for (int j = 1; j <= m; ++ j)
            if (a[i][j] == -2)///zmeu
                Q.push({poz(i, j), 0});

    ///leezmeu
    poz x;
    int dist;
    while (!Q.empty())
    {
        x = Q.front().first;
        dist = Q.front().second;
        Q.pop();

        for(int d = 0 ; d < 4 ; d++)
        {
            int inou = x.i + di[d];
            int jnou = x.j + dj[d];
            if(inside(inou , jnou) && a[inou][jnou] != -1 && a[inou][jnou] != -2 && dist + 1 <= k)
            {
                Q.push({poz(inou , jnou), dist + 1});
                a[inou][jnou] = -2;
            }
        }
    }
    lee(1 , 1);
    if (b[n][m] == 0) cout << "-1";
    else cout << b[n][m];
}