Rezolvare completă PbInfo #3380 Castel2

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

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Castel2:

#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;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #3380 Castel2

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #3380 Castel2 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!